Maximum Sum of Two Non-Overlapping Subarrays
Problem
Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen. The subarrays may appear in either order, but they must not overlap.
nums = [0, 6, 5, 2, 2, 5, 1, 9, 4], firstLen = 1, secondLen = 220def max_sum_two_no_overlap(nums, first_len, second_len):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
def best(L, M):
# L-window before M-window
max_l = best_sum = 0
for i in range(L + M, n + 1):
max_l = max(max_l, prefix[i - M] - prefix[i - M - L])
best_sum = max(best_sum, max_l + prefix[i] - prefix[i - M])
return best_sum
return max(best(first_len, second_len), best(second_len, first_len))function maxSumTwoNoOverlap(nums, firstLen, secondLen) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
function best(L, M) {
let maxL = 0, bestSum = 0;
for (let i = L + M; i <= n; i++) {
maxL = Math.max(maxL, prefix[i - M] - prefix[i - M - L]);
bestSum = Math.max(bestSum, maxL + prefix[i] - prefix[i - M]);
}
return bestSum;
}
return Math.max(best(firstLen, secondLen), best(secondLen, firstLen));
}class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
return Math.max(best(prefix, n, firstLen, secondLen),
best(prefix, n, secondLen, firstLen));
}
private int best(int[] prefix, int n, int L, int M) {
int maxL = 0, bestSum = 0;
for (int i = L + M; i <= n; i++) {
maxL = Math.max(maxL, prefix[i - M] - prefix[i - M - L]);
bestSum = Math.max(bestSum, maxL + prefix[i] - prefix[i - M]);
}
return bestSum;
}
}int best(vector<int>& prefix, int n, int L, int M) {
int maxL = 0, bestSum = 0;
for (int i = L + M; i <= n; i++) {
maxL = max(maxL, prefix[i - M] - prefix[i - M - L]);
bestSum = max(bestSum, maxL + prefix[i] - prefix[i - M]);
}
return bestSum;
}
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
return max(best(prefix, n, firstLen, secondLen),
best(prefix, n, secondLen, firstLen));
}Explanation
We need two windows of fixed lengths that do not touch, with the biggest combined sum. The tricky part is they can appear in either order, so we just solve "the L-window comes before the M-window" twice — once each way — and take the better result.
To get any window's sum instantly, we precompute a prefix sum array where prefix[i] is the total of the first i elements. Then the sum of any slice is prefix[hi] - prefix[lo] in constant time.
Inside best(L, M) we slide the M-window from left to right. For each position we track maxL, the best L-window sum lying entirely to the left of the current M-window. Adding maxL to the current M-window sum gives a candidate answer, and we keep the maximum. Because maxL only ever looks behind, the two windows never overlap.
Example: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2. Picking [9] and [6,5] gives 9 + 11 = 20, the best non-overlapping pair, so the answer is 20.