Find 3 non-overlapping subarrays of length k with maximum total sum. Return starting indices.
Input: nums=[1,2,1,2,6,7,5,1], k=2 → Output: [0,3,5]
Input: nums=[1,2,1,2,1,2,1,2,1], k=2 → Output: [0,2,4]
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
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)