Maximum Sum of Two Non-Overlapping Subarrays

Medium
1132.

Maximum Sum of Two Non-Overlapping Subarrays

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.

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 <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} firstLen
 * @param {number} secondLen
 * @return {number}
 */
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Hints for Maximum Sum of Two Non-Overlapping Subarrays

  1. Hint 1

    Prefix sums give any window's total in O(1).

  2. 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.

  3. Hint 3

    Sweep the end index once, maintaining the best firstLen window seen so far to the left and the best secondLen window 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

  1. Build prefix sums P with P[0] = 0, so a window [s, e) sums to P[e] - P[s].
  2. Let L = firstLen, M = secondLen. Start with best = P[L + M], bestL = P[L], bestM = P[M].
  3. For each end i from L + M + 1 to n: update bestL with the L-window ending at i - M, update bestM with the M-window ending at i - L.
  4. Then best = max(best, bestL + (M-window ending at i), bestM + (L-window ending at i)).
  5. 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 "firstLen window 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 (or i - L) or earlier.
  • The initial value P[L + M] covers the case where the two windows exactly tile the first L + M elements 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 best

Java

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