Maximum Sum of 3 Non-Overlapping Subarrays [Hard] — Sliding Window + DP

Problem Statement

Find three non-overlapping subarrays of length k with maximum sum. Return their starting indices (lexicographically smallest if tie).

Input: nums=[1,2,1,2,6,7,5,1], k=2 → Output: [0,3,5]

Intuition

Compute all window sums of size k.
For each index, compute left[i] = index of max window sum in [0..i].
For each index, compute right[i] = index of max window sum in [i..n].
Iterate middle window; combine left and right best.

Solutions

Python

def maxSumOfThreeSubarrays(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    sums = [sum(nums[:k])]
    for i in range(1, n-k+1):
        sums.append(sums[-1] - nums[i-1] + nums[i+k-1])

    m = len(sums)
    left = [0] * m   # best left index up to i
    best = 0
    for i in range(m):
        if sums[i] > sums[best]: best = i
        left[i] = best

    right = [0] * m  # best right index from i
    best = m - 1
    for i in range(m-1, -1, -1):
        if sums[i] >= sums[best]: best = i
        right[i] = best

    ans = [-1, -1, -1]
    best_sum = 0
    for mid in range(k, m-k):
        l, r = left[mid-k], right[mid+k]
        total = sums[l] + sums[mid] + sums[r]
        if total > best_sum:
            best_sum = total
            ans = [l, mid, r]
    return ans

C++

vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    int n=nums.size(), m=n-k+1;
    vector<int> sums(m);
    int s=0; for(int i=0;i<k;i++) s+=nums[i]; sums[0]=s;
    for(int i=1;i<m;i++) sums[i]=sums[i-1]-nums[i-1]+nums[i+k-1];
    vector<int> left(m),right(m);
    for(int i=0,b=0;i<m;i++){if(sums[i]>sums[b])b=i;left[i]=b;}
    for(int i=m-1,b=m-1;i>=0;i--){if(sums[i]>=sums[b])b=i;right[i]=b;}
    vector<int> ans={-1,-1,-1}; int best=0;
    for(int mid=k;mid<m-k;mid++){
        int l=left[mid-k],r=right[mid+k];
        int tot=sums[l]+sums[mid]+sums[r];
        if(tot>best){best=tot;ans={l,mid,r};}
    }
    return ans;
}

Complexity

Time: O(n)
Space: O(n)