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] <= 1000The key idea in #1031 Maximum Sum of Two Non-Overlapping Subarrays is to efficiently evaluate two fixed-length subarrays that do not overlap while maximizing their combined sum. A brute-force approach would check all pairs of subarrays, but that would be inefficient for large arrays.
An optimal strategy combines sliding window and dynamic programming. First, use a sliding window to compute the sum of subarrays of given lengths. Then maintain the maximum sum seen so far for the first subarray while scanning the array for the second one. This ensures the two segments do not overlap. Because the two subarrays can appear in either order (L before M or M before L), evaluate both possibilities.
By tracking prefix best values and updating window sums efficiently, we can compute the result in linear time. This approach avoids recomputation and keeps the algorithm efficient even for large inputs.
Time Complexity: O(n)
Space Complexity: O(1) to O(n) depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Prefix Maximum (evaluate both subarray orders) | O(n) | O(1) - O(n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
We can use prefix sums to calculate any subarray sum quickly. For each L length subarray, find the best possible M length subarray that occurs before and after it.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The two subarrays can appear in either order in the array. One case may have the first-length subarray before the second, while another may have the opposite arrangement. Evaluating both ensures the algorithm finds the true maximum sum.
Yes, variations of this problem appear in coding interviews at companies like Amazon, Google, and Facebook. It tests understanding of sliding window optimization, prefix sums, and dynamic programming patterns.
Arrays and prefix calculations are typically sufficient for this problem. Sliding window techniques help compute subarray sums efficiently, while prefix maximum tracking helps maintain the best previous subarray without overlap.
The optimal approach uses a combination of sliding window and dynamic programming. You track the best sum of the first subarray while scanning for the second, ensuring the two segments do not overlap. Evaluating both possible orders of the subarrays guarantees the maximum result.