689. Maximum Sum of 3 Non-Overla

居然有被考到，但是似懂非懂的

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n];//sum of nums[0] to nums[i]
        int[] left = new int[n];
        int[] right = new int[n];
        sums[0] = nums[0];
        for (int i = 1; i < n; i++){
            sums[i] = sums[i - 1] + nums[i];
        }
        int max = Integer.MIN_VALUE;
        //left[i]: the starting index of max sum subarray before i
        for (int i = k - 1; i < n; i++){
            int sum = sums[i] - sums[i - k + 1]  + nums[i - k + 1];// ??
            if (sum > max){
                max = sum;
                left[i] = i - k + 1;
            } else {
                left[i] = left[i - 1];
            }
        }
        max = Integer.MIN_VALUE;
        //right[i]: the starting index of max sum subarray after i
        for (int i = n - k; i >= 0; i--){
            int sum = sums[i + k - 1] - sums[i] + nums[i];
            if (sum > max){
                max = sum;
                right[i] = i;
            } else {
                right[i] = right[i + 1];
            }
        }
        int[] res = new int[3];
        max = Integer.MIN_VALUE;
        for (int i = k; i <= n - 2*k; i++){
            int leftStart = left[i - 1];
            int rightStart = right[i + k];
            int sum = sums[leftStart + k - 1] - sums[leftStart] + nums[leftStart];//?
            sum += sums[rightStart + k - 1] - sums[rightStart] + nums[rightStart];
            sum += sums[i + k - 1] - sums[i] + nums[i];
            if (sum > max){
                max = sum;
                res[0] = leftStart;
                res[1] = i;
                res[2] = rightStart;
            }
        }
        return res;
    }
}