#1031

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Sum of Two Non-Overlapping Subarrays

Find the maximum sum of two non-overlapping subarrays by efficiently using state transition dynamic programming.

array dynamic programming sliding window

Problem Statement

Given an integer array nums and two integers firstLen and secondLen, determine the largest possible sum of elements from two non-overlapping subarrays with lengths firstLen and secondLen. The subarrays can appear in any order, but they must not overlap, and each subarray is contiguous.

Return the maximum sum achievable by choosing the two subarrays according to the constraints. Use examples like nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2 to verify correctness and edge cases.

Examples

Example 1

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2

Output: 20

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

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

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

Solution Approach

Prefix Sum Computation

Compute a prefix sum array to quickly get the sum of any subarray. This allows O(1) calculation of subarray sums once the prefix sums are prepared, which is critical for efficient dynamic programming.

Dynamic Programming State Transition

Use DP to track the maximum sum for subarrays ending before each index for the first length, then combine with candidate second-length subarrays. Update states to reflect the highest sum without overlap at each step.

Handling Both Orders

Evaluate scenarios where the first-length subarray comes before the second-length and vice versa. The final result is the maximum sum from both configurations, ensuring no overlapping subarrays are counted.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for computing prefix sums and iterating through the array to find optimal subarrays, with n being the length of nums. Space complexity is O(n) to store prefix sums and DP states.

What Interviewers Usually Probe

Prefers using prefix sums to avoid repeated subarray sum calculations.
Checks if you handle both subarray orderings for firstLen and secondLen.
Wants attention to non-overlapping constraint in state updates.

Common Pitfalls or Variants

Common pitfalls

Ignoring the non-overlapping constraint between the two subarrays.
Only checking one ordering of firstLen and secondLen, missing better sums.
Incorrectly computing subarray sums without prefix sums, causing timeouts.

Follow-up variants

Maximum sum of k non-overlapping subarrays of different lengths.
Find subarrays with a maximum product instead of sum while keeping them non-overlapping.
Allow subarrays to overlap partially with a penalty function instead of strict exclusion.

FAQ

How do I handle overlapping subarrays for this problem?

Use prefix sums and track the maximum sum for subarrays ending before the current index to ensure no overlap occurs.

Can the subarrays be in any order?

Yes, evaluate both orders of firstLen and secondLen subarrays and take the maximum sum among them.

Why is state transition dynamic programming useful here?

It efficiently combines prefix sums and maximum sums for valid subarray placements without redundant computations.

What is the time complexity for this approach?

Computing prefix sums and iterating to evaluate subarrays gives O(n) time complexity, with n being the length of nums.

What edge cases should I test?

Test small arrays, subarrays at the beginning or end, and cases where firstLen equals secondLen to ensure non-overlapping constraints are respected.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = t = 0
        i = firstLen
        while i + secondLen - 1 < n:
            t = max(t, s[i] - s[i - firstLen])
            ans = max(ans, t + s[i + secondLen] - s[i])
            i += 1
        t = 0
        i = secondLen
        while i + firstLen - 1 < n:
            t = max(t, s[i] - s[i - secondLen])
            ans = max(ans, t + s[i + firstLen] - s[i])
            i += 1
        return ans

Continue Practicing

#978 longest turbulent subarray #718 maximum length of repeated subarray #689 maximum sum of 3 non overlapping subarrays