Maximum Sum of Two Non-Overlapping Subarrays - Solution & Explanation
Problem Statement
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 <= 10002 <= firstLen + secondLen <= 1000firstLen + secondLen <= nums.length <= 10000 <= nums[i] <= 1000
Approach Overview
Problem Overview: You are given an integer array and two lengths L and M. The task is to find two non-overlapping subarrays of these lengths whose combined sum is maximum. The order can be either L before M or M before L, but the subarrays must not overlap.
Approach 1: Prefix Sum and Sliding Window Technique (O(n) time, O(n) space)
This approach combines array prefix sums with a sliding window scan. First compute a prefix sum array so any subarray sum can be retrieved in O(1). Then iterate through the array while tracking the best possible subarray of length L seen so far before a window of length M. For each position, calculate the sum of the current M-length window and add it to the maximum L-length window found earlier. Repeat the process with the order reversed (M before L) because the larger result might come from either arrangement.
The key insight is that you never need to recompute previous windows. Instead, maintain a running maximum for the earlier window and update the answer while sliding the later window forward. This produces a linear scan of the array and avoids nested loops. Time complexity is O(n) and extra space is O(n) for the prefix sums (or O(1) if window sums are maintained incrementally).
Approach 2: Dynamic Programming Approach (O(n) time, O(n) space)
This approach uses dynamic programming to precompute the best subarray sums from both directions. Build two helper arrays: leftMax[i] stores the maximum sum of an L-length subarray ending at or before index i, and rightMax[i] stores the maximum sum of an M-length subarray starting at or after index i. These arrays allow you to combine non-overlapping segments efficiently.
After filling these arrays, iterate across the split point between the two subarrays. For every index, combine the best left segment with the best right segment. Run the same process again with L and M swapped to cover both possible orders. The DP arrays remove the need for recomputation and keep the algorithm linear.
This method is slightly more explicit than the sliding window technique because it stores intermediate results. It is useful when you want a clear separation between prefix computations and the final aggregation step.
Recommended for interviews: The prefix sum + sliding window solution is what most interviewers expect. It shows that you recognize the sliding window pattern and can optimize subarray calculations to O(n). Explaining the brute-force idea (checking all pairs of subarrays in O(n^2)) demonstrates understanding, but implementing the linear-time window technique shows strong problem-solving skills.
Approach 1: Prefix Sum and Sliding Window Technique
This approach uses prefix sums to calculate the sums of possible subarrays efficiently and then utilizes the sliding window technique to maintain maximum sums of the first and second subarrays non-overlappingly.
The solution calculates the prefix sum of the array to efficiently compute sums of any subarray. Two separate iterations are used: one to consider the case when the first subarray comes before the second and another when the second comes before the first. In each case, track the maximum subarray sum for one length while evaluating the other sum dynamically to ensure they do not overlap.
Complexity
Time Complexity: O(n), where n is the length of the array, as we only iterate over it a few times. Space Complexity: O(n), used by the prefix sum array.
Approach 2: Dynamic Programming Approach
This approach uses dynamic programming to keep track of maximum sums of subarrays of specific lengths at each position in the array. This strategy allows for efficient computation of non-overlapping subarray sums by leveraging previous maximum computations.
Here, as we loop through the array, we maintain maximum sums for subarrays of length L and M using dynamic programming. At each step, the optimum result is updated by combining these maximums appropriately, ensuring the subarrays do not overlap.
Complexity
Time Complexity: O(n), as the array is processed linearly. Space Complexity: O(1), since only a few variables for max sums are maintained.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Sliding Window Technique | Time Complexity: O(n), where n is the length of the array, as we only iterate over it a few times. Space Complexity: O(n), used by the prefix sum array. |
| Dynamic Programming Approach | Time Complexity: O(n), as the array is processed linearly. Space Complexity: O(1), since only a few variables for max sums are maintained. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (check all subarray pairs) | O(n^2) | O(1) | Conceptual baseline or very small arrays |
| Prefix Sum + Sliding Window | O(n) | O(n) or O(1) | Best general solution and commonly expected in interviews |
| Dynamic Programming with Left/Right Max Arrays | O(n) | O(n) | When you want explicit precomputed maximum segments from both directions |
Video Solution
Maximum Sum Of Two Non Overlapping Subarrays | Dynamic Programming-1-1-0 • Pepcoding • 21,379 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Sum of Two Non-Overlapping Subarrays easy or hard?
Maximum Sum of Two Non-Overlapping Subarrays Python/Java solution
How to solve Maximum Sum of Two Non-Overlapping Subarrays in O(n)?
What is the best approach for Maximum Sum of Two Non-Overlapping Subarrays?
Is Maximum Sum of Two Non-Overlapping Subarrays asked at Google/Amazon/Meta?
What data structure is used in Maximum Sum of Two Non-Overlapping Subarrays?
What is the time complexity of Maximum Sum of Two Non-Overlapping Subarrays?
Ready to solve this problem?
Practice Maximum Sum of Two Non-Overlapping Subarrays with our built-in code editor and test cases.
Practice on FleetCode