Scale Engineer

Maximum Sum of Two Non-Overlapping Subarrays

Med
#0985Time: O(N), where N is the length of `nums`. We make a single pass to compute prefix sums, and then two more passes inside the helper function.Space: O(N) to store the prefix sum array.
Patterns
Sliding WindowDynamic Programming
Data structures
Array

Prompt

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 array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [0,3,8] with length 3.

 

Constraints:

  • 1 <= firstLen, secondLen <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach improves upon the brute force by avoiding redundant calculations. It breaks the problem into two cases: the first subarray appears before the second, and vice-versa. It then uses dynamic programming ideas to solve each case in linear time.

Algorithm

  • Create a helper function solve(prefix, L, M).
  • Inside solve:
    • Initialize maxLsum = 0 and maxTotal = 0.
    • Iterate i from L + M to n:
      • Calculate sum of L-subarray ending at i - M - 1: sumL = prefix[i - M] - prefix[i - M - L].
      • Update maxLsum = max(maxLsum, sumL).
      • Calculate sum of M-subarray ending at i - 1: sumM = prefix[i] - prefix[i - M].
      • Update maxTotal = max(maxTotal, maxLsum + sumM).
    • Return maxTotal.
  • In the main function:
    • Calculate prefix sums for nums.
    • Call res1 = solve(prefix, firstLen, secondLen).
    • Call res2 = solve(prefix, secondLen, firstLen).
    • Return max(res1, res2).

Walkthrough

The core idea is to solve two separate, symmetric problems and take the maximum of their results:

  1. Max sum with a firstLen subarray appearing before a secondLen subarray.
  2. Max sum with a secondLen subarray appearing before a firstLen subarray.

Let's focus on case 1. We can write a helper function solve(L, M) for this. We iterate through the array, considering each possible position for the M-length subarray. For each position, we need the maximum sum of an L-length subarray that appears entirely before it. To do this efficiently, as we iterate from left to right with a split point, we can keep track of the maximum L-length subarray sum seen so far to the left of the split point. We first compute a prefix sum array to get subarray sums in O(1). The solve(L, M) function works as follows:

  • Initialize maxL (max sum of an L-subarray) and maxTotal.
  • Iterate i from L + M to n. The index i represents the end of the combined window.
  • The M-length subarray ends at i-1. Its sum is sumM.
  • The L-length subarray must end at or before i - M - 1. We update maxL by considering the new L-length subarray that just became available (the one ending at i - M - 1).
  • We then update maxTotal with maxL + sumM.

The final result is max(solve(firstLen, secondLen), solve(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(            findMaxSum(prefix, firstLen, secondLen),            findMaxSum(prefix, secondLen, firstLen)        );    }     private int findMaxSum(int[] prefix, int L, int M) {        int n = prefix.length - 1;        int maxL = 0;        int maxTotal = 0;        // Window of L+M, M is the second subarray        for (int i = L + M; i <= n; i++) {            // Max L-sum subarray in the first part [0, i-M-1]            int sumL = prefix[i - M] - prefix[i - M - L];            maxL = Math.max(maxL, sumL);                        // M-sum subarray in the second part [i-M, i-1]            int sumM = prefix[i] - prefix[i - M];            maxTotal = Math.max(maxTotal, maxL + sumM);        }        return maxTotal;    }}

Complexity

Time

O(N), where N is the length of `nums`. We make a single pass to compute prefix sums, and then two more passes inside the helper function.

Space

O(N) to store the prefix sum array.

Trade-offs

Pros

  • Much more efficient than the brute-force approach with a linear time complexity.

Cons

  • Requires extra space for the prefix sum array.

Solutions

class Solution {public  int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {    int n = nums.length;    int[] s = new int[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + nums[i];    }    int ans = 0;    for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {      t = Math.max(t, s[i] - s[i - firstLen]);      ans = Math.max(ans, t + s[i + secondLen] - s[i]);    }    for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {      t = Math.max(t, s[i] - s[i - secondLen]);      ans = Math.max(ans, t + s[i + firstLen] - s[i]);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem