Maximum Sum of 3 Non-Overlapping Subarrays.cpp

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int len = nums.size();
        if(len < 3 * k)return {};
        //store index, use presum to get the value
        vector<int> left(len, -1), right(len, -1), presums(len + 1, 0);
        int sum = 0;
        //init presum
        for(int i = 0; i < len; ++i)
        {
            sum += nums[i];
            presums[i + 1] = sum;
        }
        //left to right
        for(int i = k - 1; i < len; ++i)
        {
            if(i == k - 1){left[i] = i; continue;}
            int currSum = presums[i + 1] - presums[i + 1 - k];
            int currMax = presums[left[i - 1] + 1] - presums[left[i - 1] + 1 - k];
            left[i] = currSum > currMax? i : left[i - 1];
        }
        //right to left
        for(int i = len - k; i >= 0; --i)
        {
            if(i == len - k){right[i] = i; continue;}
            int currSum = presums[i + k] - presums[i];
            int currMax = presums[right[i + 1] + k] - presums[right[i + 1]];
            right[i] = currSum >= currMax? i: right[i + 1]; 
        }
        //middle
        int maxVal = INT_MIN;
        vector<int> res;
        for(int i = 2 * k - 1; i < len - k; ++i)
        {
            int leftIdx = left[i - k], rightIdx = right[i + 1];
            int leftSum = presums[leftIdx + 1] - presums[leftIdx + 1 - k];
            int rightSum = presums[rightIdx + k] - presums[rightIdx];
            int middle = presums[i + 1] - presums[i + 1 - k];
            int currSum = leftSum + middle + rightSum;
            if(currSum > maxVal)
            {
                maxVal = currSum;
                res = {leftIdx - k + 1, i - k + 1, rightIdx};
            }
        }
        return res;
    }
};