Maximum Sum of Two Non-Overlapping Subarrays: Prefix Sum + Sliding Window

Given an integer array nums and two integers firstLen and secondLen, find two non-overlapping subarrays with lengths firstLen and secondLen that have the maximum total sum. The subarrays can appear in either order (the firstLen subarray does not need to come before the secondLen subarray).

This is LeetCode 1031: Maximum Sum of Two Non-Overlapping Subarrays, and it combines prefix sums with a running maximum in a clean one-pass pattern. Once you see the trick of splitting the problem into two cases, the solution falls into place.

Why this problem matters

This problem teaches you a technique that shows up constantly in subarray optimization: use prefix sums to compute window sums in O(1), then maintain a running best as you slide through positions. It is a natural step up from Maximum Subarray, where Kadane's algorithm tracks one running value. Here you track two windows, and the key is handling the two possible orderings.

The pattern generalizes. Once you can handle two non-overlapping windows, you are well positioned to tackle the harder three-window variant, which uses the same prefix sum foundation but adds a left-right decomposition.

The key insight

The two subarrays cannot overlap, so one must come before the other. That gives you exactly two cases:

1. The firstLen window appears to the left of the secondLen window.
2. The secondLen window appears to the left of the firstLen window.

For each case, you slide the right window across the array. As you do, you maintain a running maximum of the best left window that ends before the right window starts. At each position, the candidate answer is best_left_sum + current_right_sum. You take the maximum across all positions, then take the maximum of both cases.

The prefix sum array lets you compute any window sum in O(1), so the entire algorithm runs in O(n) time.

The solution

def maxSumTwoNoOverlap(nums, firstLen, secondLen):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    def window(i, length):
        return prefix[i + length] - prefix[i]

    def best(lenA, lenB):
        max_a = window(0, lenA)
        result = max_a + window(lenA, lenB)
        for i in range(lenA + 1, n - lenB + 1):
            max_a = max(max_a, window(i - lenA, lenA))
            result = max(result, max_a + window(i, lenB))
        return result

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

The code does three things. First, it builds the prefix sum array so that any window sum is a single subtraction. Second, the best(lenA, lenB) helper slides the lenB window across all valid positions while keeping a running max of the best lenA window that fits to its left. Third, it calls best twice (once for each ordering) and returns the larger result.

Inside the best function, max_a tracks the maximum sum of any lenA window ending at or before the start of the current lenB window. As the lenB window moves one step to the right, a new lenA window becomes available (the one that ends exactly where the lenB window used to start). You compare that new window against max_a and update.

Visual walkthrough

The walkthrough shows the two-case strategy in action. In Case 1, the firstLen window slides first and the algorithm finds a best total of 16. In Case 2, the secondLen window slides first and finds a total of 20. The answer is max(16, 20) = 20.

Complexity analysis

Time: O(n). Building the prefix sum array takes O(n). Each call to best scans the array once in O(n). Two calls gives O(2n) = O(n). Total: O(n).

Space: O(n). The prefix sum array is the only extra allocation, and it has n+1 elements. Everything else uses O(1) space. You could reduce space to O(1) by computing window sums with a running total instead of a prefix array, but the prefix approach is cleaner and the O(n) space is rarely a concern.

The building blocks

1. Prefix sums for subarray sums

A prefix sum array lets you compute the sum of any contiguous subarray in O(1). Build it once in O(n):

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]

Then prefix[j] - prefix[i] gives the sum of nums[i..j-1]. This is the same building block used in Subarray Sum Equals K, where you combine prefix sums with a hash map. Here you pair it with a sliding window instead.

2. Running maximum while sliding

As you slide one window across the array, you maintain a running max of the best window that fits in the remaining space:

max_a = window(0, lenA)
for i in range(lenA + 1, n - lenB + 1):
    max_a = max(max_a, window(i - lenA, lenA))
    result = max(result, max_a + window(i, lenB))

This is the same technique behind Maximum Subarray, where Kadane's algorithm maintains a running best as it scans. The difference is that here you are tracking the best fixed-length window rather than a variable-length subarray. The idea is identical: carry the best answer forward so you never need to look back.

Edge cases

• firstLen + secondLen == n: the two windows cover the entire array, so there is only one valid placement. Make sure your loop handles this boundary.
• firstLen == secondLen: both windows have the same length. The algorithm still works, but both calls to best might return the same value.
• All equal elements like [3, 3, 3, 3] with firstLen=1, secondLen=2: every placement gives the same sum. The algorithm handles this correctly since max is stable.
• Single large element: if one element dominates, the optimal placement puts the shorter window on that element. The two-case approach ensures this is found.
• Minimum array length: the array has at least firstLen + secondLen elements (guaranteed by the constraints), so you always have at least one valid placement.

From understanding to recall

You now understand the two-case prefix sum approach: build prefix sums, slide the right window while tracking the best left window, and take the max of both orderings. The logic is clean and the code is short. But will you remember to handle both orderings during an interview? Will you remember how the running max updates as the window slides?

Spaced repetition bridges this gap. You revisit the prefix sum + running max pattern at increasing intervals, writing the solution from scratch each time. After a few reps, the two-case decomposition and the sliding update become automatic.

The prefix sum building block and the running maximum pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Maximum Subarray - The foundation: Kadane's algorithm uses the same running-max-while-scanning pattern with a single window
• Maximum Sum Circular Subarray - Another "handle two cases" problem that extends Kadane's to circular arrays
• Subarray Sum Equals K - Prefix sums paired with a hash map, the other major prefix sum pattern