689. Maximum Sum of 3 Non-Overlapping Subarrays

T: O(n)
S: O(n)

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int subSumLen = n - k + 1;
        int[] subSum = new int[subSumLen];
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        // find subarray_sum
        subSum[0] = sum; // [0 1] 2
        for (int i = k; i < n; i++) {
            sum -= nums[i - k]; // sum -= nums[k - 2] -> nums[2-2] = nums[0]
            sum += nums[i]; // sum += nums[i] = nums[k] = nums[2]
            subSum[i - k + 1] = sum; // subSum[k-k+1] = sunSum[1]
        }

        // find max subarray sum from left, record index
        int[] maxLeftIdx = new int[subSumLen];
        for (int i = 1; i < subSumLen; i++) {
            if (subSum[i] > subSum[maxLeftIdx[i-1]]) {
                maxLeftIdx[i] = i;
            } else {
                maxLeftIdx[i] = maxLeftIdx[i-1];
            }
        }

        // find max subarray sum from right, record index
        int[] maxRight = new int[subSumLen];
        maxRight[subSumLen-1] = subSumLen-1;

        for (int i = subSumLen - 2; i >= 0; i--) {
            if (subSum[i] >= subSum[maxRight[i+1]]) { // why here has a "="" , because return the lexicographically smallest one., so if there is equal sum but smaller index, we pick smaller index 
                maxRight[i] = i;
            } else {
                maxRight[i] = maxRight[i+1];
            }
        }

        int[] result = new int[3];
        int max = 0;

        // find i-k(range), i, i+k (range) -> i-k, i+k is the (range)idx with maxSubSum
        for (int i = k; i < subSumLen - k; i++) {
            int threeSum = subSum[maxLeftIdx[i-k]] + subSum[i] + subSum[maxRight[i+k]];
            if (threeSum > max) {
                result = new int[]{maxLeftIdx[i-k], i, maxRight[i+k]};
                max = threeSum;
            }
        }
        return result;
    }
}

/***
find three "non-overlapping" subarrays of length k with maximum sum

 x     x   x starting point     
 0 1 2 3 4 5 6 7
[1,2,1,2,6,7,5,1]
 x x   x x x x
   
 x.  x.  x  
 0 1 2 3 4 5 6 7 8
[1,2,1,2,1,2,1,2,1]

save sum for
n - k + 1 subarray with len k
[1,2,1,2,6,7,5,1]
 [. ]
   [ ]
             [  ] 

subsum

leftMax
rightMax

find max( subsum[leftMax[i]] + subsum[i] + subsum[rightMax[i]] )

and record that 3 index for ans


T: O(n)
S: O(n)

[1,2,1,2,1,2,1,2,1]

 3 3 3 3 3 3 3 3  
 */