Maximum Sum of 3 Non-Overlapping Subarrays
Problem
Find indices of 3 non-overlapping length-k subarrays with maximum total sum (lex-smallest indices on ties).
nums=[1,2,1,2,6,7,5,1] k=2[0,3,5]def max_sum_of_3(nums, k):
n = len(nums); s = [0] * (n - k + 1)
cur = sum(nums[:k]); s[0] = cur
for i in range(1, n - k + 1): cur += nums[i + k - 1] - nums[i - 1]; s[i] = cur
left = [0] * len(s); best = 0
for i in range(len(s)):
if s[i] > s[best]: best = i
left[i] = best
right = [0] * len(s); best = len(s) - 1
for i in range(len(s) - 1, -1, -1):
if s[i] >= s[best]: best = i
right[i] = best
ans = None; best_sum = -1
for j in range(k, len(s) - k):
l, r = left[j - k], right[j + k]
t = s[l] + s[j] + s[r]
if t > best_sum: best_sum = t; ans = [l, j, r]
return ansfunction maxSumOfThreeSubarrays(nums, k) {
const n = nums.length;
const s = new Array(n - k + 1); let cur = 0;
for (let i = 0; i < k; i++) cur += nums[i];
s[0] = cur;
for (let i = 1; i < s.length; i++) { cur += nums[i + k - 1] - nums[i - 1]; s[i] = cur; }
const left = new Array(s.length); let best = 0;
for (let i = 0; i < s.length; i++) { if (s[i] > s[best]) best = i; left[i] = best; }
const right = new Array(s.length); best = s.length - 1;
for (let i = s.length - 1; i >= 0; i--) { if (s[i] >= s[best]) best = i; right[i] = best; }
let ans = null, bs = -1;
for (let j = k; j < s.length - k; j++) {
const l = left[j - k], r = right[j + k];
const t = s[l] + s[j] + s[r];
if (t > bs) { bs = t; ans = [l, j, r]; }
}
return ans;
}int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length, m = n - k + 1; int[] s = new int[m]; int cur = 0;
for (int i = 0; i < k; i++) cur += nums[i]; s[0] = cur;
for (int i = 1; i < m; i++) { cur += nums[i + k - 1] - nums[i - 1]; s[i] = cur; }
int[] L = new int[m]; int best = 0;
for (int i = 0; i < m; i++) { if (s[i] > s[best]) best = i; L[i] = best; }
int[] R = new int[m]; best = m - 1;
for (int i = m - 1; i >= 0; i--) { if (s[i] >= s[best]) best = i; R[i] = best; }
int[] ans = null; int bs = -1;
for (int j = k; j < m - k; j++) {
int l = L[j - k], r = R[j + k]; int t = s[l] + s[j] + s[r];
if (t > bs) { bs = t; ans = new int[]{l, j, r}; }
}
return ans;
}vector maxSumOfThreeSubarrays(vector& nums, int k) {
int n = nums.size(), m = n - k + 1; vector s(m); int cur = 0;
for (int i = 0; i < k; i++) cur += nums[i]; s[0] = cur;
for (int i = 1; i < m; i++) { cur += nums[i + k - 1] - nums[i - 1]; s[i] = cur; }
vector L(m); int best = 0;
for (int i = 0; i < m; i++) { if (s[i] > s[best]) best = i; L[i] = best; }
vector R(m); best = m - 1;
for (int i = m - 1; i >= 0; i--) { if (s[i] >= s[best]) best = i; R[i] = best; }
vector ans; int bs = -1;
for (int j = k; j < m - k; j++) {
int l = L[j - k], r = R[j + k]; int t = s[l] + s[j] + s[r];
if (t > bs) { bs = t; ans = {l, j, r}; }
}
return ans;
} Explanation
We need three non-overlapping length-k windows with the biggest combined sum. The trick is to fix the middle window and quickly grab the best left window to its left and the best right window to its right.
First we precompute s[i], the sum of the window starting at index i, using a sliding window so each one is O(1) after the first. Then we build two helper arrays: left[i] = index of the best window in s[0..i], and right[i] = index of the best window in s[i..end].
Now for every possible middle start j, the best left is left[j-k] and the best right is right[j+k] (the -k and +k guarantee no overlap). We add the three sums and keep the maximum. The >= in the right scan biases toward smaller indices, giving the lexicographically smallest answer on ties.
Example: nums=[1,2,1,2,6,7,5,1], k=2. Window sums are [3,3,3,8,13,12,6]. Fixing the middle at j=3 (sum 8) pairs with left window 0 and right window 5, total 3+8+12=23 — the best — at indices [0,3,5].
All the precomputation and the final scan are linear, so the whole solution is O(n).