Maximum Sum of 3 Non-Overlapping Subarrays — Solution
Maximum Sum of 3 Non-Overlapping Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Sum of 3 Non-Overlapping Subarrays is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, choose three non-overlapping subarrays, each of length exactly k, whose elements add up to the largest possible total.
Return the 0-indexed starting positions of the three subarrays in increasing order. When several choices reach the same maximum total, return the one whose list of positions is lexicographically smallest.
Example 1
Input: nums = [3,1,3,1,8,9,4,1], k = 2
Output: [0,3,5]
Explanation: The window sums are `[4,4,4,9,17,13,5]`. The best total is 26, reached by `[0,3,5]`, `[1,3,5]`, `[0,4,6]` and others; `[0,3,5]` is the smallest.
Example 2
Input: nums = [2,2,2,2,2,2], k = 1
Output: [0,1,2]
Explanation: Every choice totals 6, so the earliest positions win.
Example 3
Input: nums = [4,5,10,6,11,17,4,11,1,3], k = 1
Output: [4,5,7]
Explanation: The three largest single values are 11, 17 and 11.
Constraints
1 <= nums.length <= 2 * 10^41 <= nums[i] < 2^161 <= k <= floor(nums.length / 3)
Hints for Maximum Sum of 3 Non-Overlapping Subarrays
Hint 1
Precompute the sum of every window of length
k. Now pick three window startsa < b < cwithb ≥ a + kandc ≥ b + k.Hint 2
Fix the middle window
b. The best left window is the best one starting anywhere in[0, b - k]; the best right window is the best one starting in[b + k, last].Hint 3
Precompute the position of the best window on every prefix and on every suffix — keeping the leftmost one on ties — then scan
bfrom left to right and replace the answer only on a strictly larger total.
How to solve Maximum Sum of 3 Non-Overlapping Subarrays
Once window sums are known, the three windows interact only through the middle one: for a fixed middle start b, the left and right choices are independent maximisations over a prefix and a suffix of the window array. Prefix and suffix argmax tables make each middle choice O(1).
Approach
- Compute
win[i], the sum ofnums[i..i+k-1], for every startiwith a sliding window. left[i]= the start of a maximal window amongwin[0..i], keeping the earliest on ties (update only on>).right[i]= the start of a maximal window amongwin[i..], keeping the earliest on ties (scanning right to left, update on>=).- For every middle start
bfromktolen(win) - 1 - k: the candidate is(left[b-k], b, right[b+k]). - Keep the first candidate with the largest total, replacing it only on a strictly larger total. Return it.
Why it works
For a fixed middle window the total is win[a] + win[b] + win[c] with a ≤ b - k and c ≥ b + k, so choosing the best a and the best c independently is optimal. The tie rules give the lexicographically smallest optimum: suppose an optimal triple used a smaller a' with a later middle b'; then a' lies outside [0, b - k] for the first optimal middle b (otherwise the leftmost-argmax rule would have chosen it), which forces a' > b - k ≥ a — a contradiction. The same argument applies to b and c.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The suffix table must prefer the leftmost window on ties — update on
>=while scanning right to left. - The outer scan must replace only on a strictly larger total, or a later middle window can displace an equally good earlier one.
- The middle start runs from
ktolen(win) - 1 - kinclusive; the constraints guarantee at least one value.
Reference solution
Python
from typing import List
def maxSumOfThreeSubarrays(nums: List[int], k: int) -> List[int]:
n = len(nums)
m = n - k + 1
win = [0] * m
s = 0
for i in range(n):
s += nums[i]
if i >= k:
s -= nums[i - k]
if i >= k - 1:
win[i - k + 1] = s
left = [0] * m
best = 0
for i in range(m):
if win[i] > win[best]:
best = i
left[i] = best
right = [0] * m
best = m - 1
for i in range(m - 1, -1, -1):
if win[i] >= win[best]:
best = i
right[i] = best
ans, top = [], -1
for b in range(k, m - k):
a, c = left[b - k], right[b + k]
total = win[a] + win[b] + win[c]
if total > top:
top = total
ans = [a, b, c]
return ansJava
public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length, m = n - k + 1;
long[] win = new long[m];
long s = 0;
for (int i = 0; i < n; i++) {
s += nums[i];
if (i >= k) s -= nums[i - k];
if (i >= k - 1) win[i - k + 1] = s;
}
int[] left = new int[m], right = new int[m];
int best = 0;
for (int i = 0; i < m; i++) {
if (win[i] > win[best]) best = i;
left[i] = best;
}
best = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (win[i] >= win[best]) best = i;
right[i] = best;
}
int[] ans = new int[3];
long top = -1;
for (int b = k; b + k < m; b++) {
int a = left[b - k], c = right[b + k];
long total = win[a] + win[b] + win[c];
if (total > top) {
top = total;
ans = new int[] { a, b, c };
}
}
return ans;
}C++
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size(), m = n - k + 1;
vector<long long> win(m);
long long s = 0;
for (int i = 0; i < n; i++) {
s += nums[i];
if (i >= k) s -= nums[i - k];
if (i >= k - 1) win[i - k + 1] = s;
}
vector<int> left(m), right(m);
int best = 0;
for (int i = 0; i < m; i++) {
if (win[i] > win[best]) best = i;
left[i] = best;
}
best = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (win[i] >= win[best]) best = i;
right[i] = best;
}
vector<int> ans;
long long top = -1;
for (int b = k; b + k < m; b++) {
int a = left[b - k], c = right[b + k];
long long total = win[a] + win[b] + win[c];
if (total > top) {
top = total;
ans = {a, b, c};
}
}
return ans;
}JavaScript
var maxSumOfThreeSubarrays = function(nums, k) {
var n = nums.length, m = n - k + 1;
var win = new Array(m);
var s = 0;
for (var i = 0; i < n; i++) {
s += nums[i];
if (i >= k) s -= nums[i - k];
if (i >= k - 1) win[i - k + 1] = s;
}
var left = new Array(m), right = new Array(m);
var best = 0;
for (var i = 0; i < m; i++) {
if (win[i] > win[best]) best = i;
left[i] = best;
}
best = m - 1;
for (var i = m - 1; i >= 0; i--) {
if (win[i] >= win[best]) best = i;
right[i] = best;
}
var ans = [], top = -1;
for (var b = k; b + k < m; b++) {
var a = left[b - k], c = right[b + k];
var total = win[a] + win[b] + win[c];
if (total > top) {
top = total;
ans = [a, b, c];
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming