LeetCode 1031: Maximum Sum of Two Non-Overlapping Subarrays

Problem Restatement

We are given an integer array nums and two integers firstLen and secondLen.

We need to return the maximum sum of elements in two non-overlapping subarrays of lengths firstLen and secondLen respectively.

The two subarrays must not overlap.

The official constraints state that 1 <= firstLen, secondLen <= 1000, 2 <= nums.length <= 1000, and -1000 <= nums[i] <= 1000.

Input and Output

Function shape:

def maxSumTwoNoOverlap(nums: list[int], firstLen: int, secondLen: int) -> int:
    ...

Examples

Example 1:

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

Best: subarray [9] (length 1) and [6, 5] (length 2). Sum = 9 + 11 = 20.

Answer:

20

Key Insight

Try both orderings: first subarray before second, and second subarray before first.

For each possible position of the second subarray, track the maximum sum of a first-length subarray to its left.

Use prefix sums to compute subarray sums in O(1).

Algorithm

Compute prefix sums. Define a helper max_sum(L, M):

• For the subarray of length M ending at each position i, compute its sum.
• Track the best sum for a subarray of length L seen before position i.
• Update the answer as best_L + window_M.

Call max_sum(firstLen, secondLen) and max_sum(secondLen, firstLen) and return the max.

Correctness

By fixing the second window and greedily picking the best first window to its left, we cover all valid non-overlapping arrangements.

Trying both orderings (first-before-second and second-before-first) ensures we don’t miss any optimal configuration.

Edge Cases

• Handle windows that never become valid.
• Update counts when both expanding and shrinking the window so stale characters do not remain in the state.
• For fixed-size windows, record the answer only after the window has exactly the required length.

Complexity

Common Pitfalls

• Do not count a window before it satisfies the required size or validity condition.
• When removing the left character, delete zero-count entries if the algorithm uses the number of keys.

Implementation

class Solution:
    def maxSumTwoNoOverlap(self, nums: list[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, v in enumerate(nums):
            prefix[i + 1] = prefix[i] + v

        def window_sum(l, r):
            return prefix[r + 1] - prefix[l]

        def best(L, M):
            result = 0
            best_L = 0
            for i in range(L + M - 1, n):
                best_L = max(best_L, window_sum(i - L - M + 1, i - M))
                result = max(result, best_L + window_sum(i - M + 1, i))
            return result

        return max(best(firstLen, secondLen), best(secondLen, firstLen))

Testing

def run_tests():
    s = Solution()

    assert s.maxSumTwoNoOverlap([0,6,5,2,2,5,1,9,4], 1, 2) == 20
    assert s.maxSumTwoNoOverlap([3,8,1,3,2,1,8,9,0], 3, 2) == 29
    assert s.maxSumTwoNoOverlap([2,1,5,6,0,9,5,0,3,8], 4, 3) == 31

    print("all tests passed")

run_tests()