Maximum Sum of 3 Non-Overlapping Subarrays

Share

Find 3 non-overlapping subarrays of length k with maximum total sum. Return starting indices.

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

Solution Approach

Precompute window sums, then best left and right index for each position. Iterate middle window.

  • Compute array of window sums (size n-k+1)
  • Precompute left[i]: best window index in [0..i]
  • Precompute right[i]: best window index in [i..end]
  • Iterate middle window: compare left[i-k]+mid+right[i+k]
  • Return best triplet indices
Java
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int n = nums.length, m = n - k + 1;
    int[] sum = new int[m];
    int s = 0;
    for (int i = 0; i < k; i++) s += nums[i];
    sum[0] = s;
    for (int i = 1; i < m; i++) { s += nums[i+k-1] - nums[i-1]; sum[i] = s; }
    int[] left = new int[m], right = new int[m];
    for (int i = 1, best = 0; i < m; i++) { if (sum[i] > sum[best]) best = i; left[i] = best; }
    for (int i = m-2, best = m-1; i >= 0; i--) { if (sum[i] >= sum[best]) best = i; right[i] = best; }
    int[] res = {-1,-1,-1};
    for (int j = k; j < m-k; j++) {
        int l = left[j-k], r = right[j+k];
        if (res[0]==-1 || sum[l]+sum[j]+sum[r] > sum[res[0]]+sum[res[1]]+sum[res[2]])
            res = new int[]{l,j,r};
    }
    return res;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)