Maximum Sum of Two Non-Overlapping Subarrays — Solution
Maximum Sum of Two Non-Overlapping Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Sum of Two Non-Overlapping Subarrays is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google, Sprinklr and Hotstar interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Sprinklr, Hotstar
- 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 nums and two lengths firstLen and secondLen, choose two non-overlapping contiguous subarrays: one of length firstLen and one of length secondLen.
The subarray of length firstLen may lie either before or after the one of length secondLen — they just may not share an index. Return the largest possible total of the elements in the two subarrays.
Example 1
Input: nums = [3,1,4,1,5,9,2,6], firstLen = 2, secondLen = 3
Output: 23
Explanation: For example `[1,4]` and `[9,2,6]`: 5 + 18 = 23.
Example 2
Input: nums = [1,2,3], firstLen = 1, secondLen = 2
Output: 6
Example 3
Input: nums = [5,0,0,5], firstLen = 1, secondLen = 1
Output: 10
Constraints
1 <= firstLen, secondLen <= 10002 <= firstLen + secondLen <= 1000firstLen + secondLen <= nums.length <= 10000 <= nums[i] <= 1000
Hints for Maximum Sum of Two Non-Overlapping Subarrays
Hint 1
Prefix sums give any window's total in O(1).
Hint 2
Fix where the later of the two windows ends. The earlier window can be any window that ends before it starts — you only need the best such one.
Hint 3
Sweep the end index once, maintaining the best
firstLenwindow seen so far to the left and the bestsecondLenwindow seen so far to the left; try both orders at every step.
How to solve Maximum Sum of Two Non-Overlapping Subarrays
Treat the two orders separately: when a window of one length ends at i, pair it with the best window of the other length that ends before it begins — a running maximum.
Approach
- Build prefix sums
PwithP[0] = 0, so a window[s, e)sums toP[e] - P[s]. - Let
L = firstLen,M = secondLen. Start withbest = P[L + M],bestL = P[L],bestM = P[M]. - For each end
ifromL + M + 1ton: updatebestLwith theL-window ending ati - M, updatebestMwith theM-window ending ati - L. - Then
best = max(best, bestL + (M-window ending at i), bestM + (L-window ending at i)). - Return
best.
Why it works
In any valid pair one window comes second. If the M-window is second and ends at i, the L-window must end at or before i - M, and bestL is exactly the maximum over those choices — similarly with roles swapped. Every pair is therefore dominated by a candidate the sweep evaluates.
Complexity
- Time —
O(n) - Space —
O(n) for the prefix sums
Pitfalls
- Considering only the order "
firstLenwindow first" misses half the answers. - The running maxima must be updated before the combination at each step, and must only include windows ending at
i - M(ori - L) or earlier. - The initial value
P[L + M]covers the case where the two windows exactly tile the firstL + Melements in either order.
Reference solution
Python
from typing import List
def maxSumTwoNoOverlap(nums: List[int], firstLen: int, secondLen: int) -> int:
n = len(nums)
p = [0] * (n + 1)
for i, v in enumerate(nums):
p[i + 1] = p[i] + v
L, M = firstLen, secondLen
best = p[L + M]
best_l = p[L]
best_m = p[M]
for i in range(L + M + 1, n + 1):
best_l = max(best_l, p[i - M] - p[i - M - L])
best_m = max(best_m, p[i - L] - p[i - L - M])
best = max(best, best_l + p[i] - p[i - M], best_m + p[i] - p[i - L])
return bestJava
public static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
int n = nums.length, L = firstLen, M = secondLen;
int[] p = new int[n + 1];
for (int i = 0; i < n; i++) p[i + 1] = p[i] + nums[i];
int best = p[L + M], bestL = p[L], bestM = p[M];
for (int e = L + M + 1; e <= n; e++) {
bestL = Math.max(bestL, p[e - M] - p[e - M - L]);
bestM = Math.max(bestM, p[e - L] - p[e - L - M]);
best = Math.max(best, Math.max(bestL + p[e] - p[e - M], bestM + p[e] - p[e - L]));
}
return best;
}C++
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
int n = nums.size(), L = firstLen, M = secondLen;
vector<int> p(n + 1, 0);
for (int i = 0; i < n; i++) p[i + 1] = p[i] + nums[i];
int best = p[L + M], bestL = p[L], bestM = p[M];
for (int e = L + M + 1; e <= n; e++) {
bestL = max(bestL, p[e - M] - p[e - M - L]);
bestM = max(bestM, p[e - L] - p[e - L - M]);
best = max(best, max(bestL + p[e] - p[e - M], bestM + p[e] - p[e - L]));
}
return best;
}JavaScript
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
var n = nums.length, L = firstLen, M = secondLen;
var p = new Array(n + 1).fill(0);
for (var i = 0; i < n; i++) p[i + 1] = p[i] + nums[i];
var best = p[L + M], bestL = p[L], bestM = p[M];
for (var e = L + M + 1; e <= n; e++) {
bestL = Math.max(bestL, p[e - M] - p[e - M - L]);
bestM = Math.max(bestM, p[e - L] - p[e - L - M]);
best = Math.max(best, bestL + p[e] - p[e - M], bestM + p[e] - p[e - L]);
}
return best;
};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