LeetCode 1031 - Maximum Sum of Two Non-Overlapping Subarrays

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem gives us an integer array nums and two fixed subarray lengths, firstLen and secondLen. We must select exactly two contiguous subarrays such that:

One subarray has length firstLen
The other subarray has length secondLen
The two subarrays do not overlap
The total sum of all elements inside both subarrays is as large as possible

The order of the subarrays does not matter. The subarray with length firstLen may appear before the subarray with length secondLen, or after it. The only requirement is that they remain completely disjoint.

The input array contains non-negative integers, which is an important detail. Since all numbers are non-negative, larger windows generally produce larger sums, and we never need to worry about negative values reducing the total unexpectedly.

The constraints tell us several useful things:

nums.length <= 1000
firstLen + secondLen <= nums.length
Every element is between 0 and 1000

An array size of 1000 is not extremely large, so even an O(n^2) solution could potentially pass. However, the problem is specifically designed to reward an optimized sliding window and prefix sum approach.

The key challenge is handling the non-overlapping condition correctly. A naive implementation may accidentally allow the two windows to intersect, especially when checking all possible positions independently.

Several edge cases are important:

The two subarrays may touch each other directly, which is allowed because touching is not overlapping.
One subarray may appear entirely before the other.
The optimal solution may place the smaller window first or second.
Arrays with many equal values can create multiple valid optimal answers.
Very small arrays where firstLen + secondLen == len(nums) leave only one possible arrangement.

Approaches

Brute Force Approach

The most direct solution is to try every possible pair of subarrays.

We can:

Enumerate every valid subarray of length firstLen
Enumerate every valid subarray of length secondLen
Check whether the two windows overlap
If they do not overlap, compute their combined sum
Track the maximum result

To compute subarray sums efficiently, we can use prefix sums so that each window sum is obtained in constant time.

This approach is correct because it explicitly checks every valid pair of subarrays, guaranteeing that the best answer will eventually be considered.

However, the time complexity becomes quadratic because there are O(n) windows for the first length and O(n) windows for the second length. Checking every pair produces O(n^2) combinations.

Although n <= 1000 is manageable, we can do better.

Optimal Approach

The key observation is that we do not need to repeatedly reconsider all previous windows.

Suppose we place the secondLen window ending at position i. Then the best firstLen window must lie completely before it. Instead of checking all previous windows every time, we can maintain:

The maximum sum of any valid firstLen window seen so far
The current secondLen window sum

This allows us to compute the best total in constant time per position.

We must also handle the opposite ordering:

firstLen before secondLen
secondLen before firstLen

Therefore, we solve the problem twice and take the maximum result.

Prefix sums make each window sum computation O(1), and a single linear scan is enough for each ordering.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks every pair of non-overlapping windows
Optimal	O(n)	O(n)	Uses prefix sums and running maximum windows

Algorithm Walkthrough

Step 1: Build Prefix Sums

Create a prefix sum array where:

prefix[i]

stores the sum of elements from index 0 through i - 1.

This allows any subarray sum to be computed in constant time:

sum(left, right) = prefix[right + 1] - prefix[left]

Using prefix sums prevents repeated summation work.

Step 2: Define a Helper Function

Create a helper function that computes:

Maximum total when:
A-length window comes before B-length window

The helper will take two parameters:

leftLen
rightLen

This function assumes the left window appears before the right window.

Step 3: Track the Best Left Window

As we scan from left to right, we maintain:

bestLeft

which stores the maximum sum of any valid leftLen window encountered so far.

At every step, this represents the best possible left-side contribution that does not overlap the current right window.

Step 4: Evaluate the Right Window

For every valid starting position of the rightLen window:

Compute the sum of the current right window
Update bestLeft using the newest possible left window
Combine:

bestLeft + currentRight

Update the global maximum

This guarantees non-overlap because the left window is always chosen entirely before the current right window begins.

Step 5: Handle Both Orders

The optimal arrangement might be:

firstLen before secondLen
secondLen before firstLen

So we compute both:

helper(firstLen, secondLen)
helper(secondLen, firstLen)

Then return the larger value.

Why it works

The algorithm maintains the invariant that bestLeft always represents the maximum possible left window sum that ends before the current right window starts. Because every right window is paired with the best compatible left window, every valid arrangement is considered exactly once. Running the process for both orderings guarantees that all possible non-overlapping configurations are covered.

Python Solution

from typing import List

class Solution:
    def maxSumTwoNoOverlap(
        self,
        nums: List[int],
        firstLen: int,
        secondLen: int
    ) -> int:

        n = len(nums)

        # Build prefix sums
        prefix = [0] * (n + 1)

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

        def window_sum(left: int, right: int) -> int:
            return prefix[right + 1] - prefix[left]

        def helper(left_len: int, right_len: int) -> int:
            best_left = 0
            answer = 0

            # right_start is the starting index
            # of the right-side window
            for right_start in range(left_len, n - right_len + 1):

                left_end = right_start - 1
                left_start = left_end - left_len + 1

                left_sum = window_sum(left_start, left_end)

                best_left = max(best_left, left_sum)

                right_end = right_start + right_len - 1
                right_sum = window_sum(right_start, right_end)

                answer = max(answer, best_left + right_sum)

            return answer

        return max(
            helper(firstLen, secondLen),
            helper(secondLen, firstLen)
        )

The implementation begins by constructing a prefix sum array. This preprocessing step allows every subarray sum to be computed in constant time, which is critical for achieving linear overall complexity.

The window_sum helper encapsulates the prefix sum calculation and improves readability. Instead of repeatedly writing prefix arithmetic throughout the algorithm, the helper centralizes the logic.

The helper function handles one ordering of the problem. It assumes the left window has length left_len and the right window has length right_len.

During iteration, best_left tracks the largest valid left window encountered so far. Since the loop scans possible right windows from left to right, every stored left window is automatically non-overlapping.

For each right window:

Compute the newest eligible left window sum
Update best_left
Compute the current right window sum
Combine them to update the answer

Finally, the algorithm evaluates both possible orderings and returns the larger result.

Go Solution

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
	n := len(nums)

	// Build prefix sums
	prefix := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + nums[i]
	}

	windowSum := func(left int, right int) int {
		return prefix[right+1] - prefix[left]
	}

	max := func(a int, b int) int {
		if a > b {
			return a
		}
		return b
	}

	helper := func(leftLen int, rightLen int) int {
		bestLeft := 0
		answer := 0

		for rightStart := leftLen; rightStart <= n-rightLen; rightStart++ {

			leftEnd := rightStart - 1
			leftStart := leftEnd - leftLen + 1

			leftSum := windowSum(leftStart, leftEnd)

			bestLeft = max(bestLeft, leftSum)

			rightEnd := rightStart + rightLen - 1
			rightSum := windowSum(rightStart, rightEnd)

			answer = max(answer, bestLeft+rightSum)
		}

		return answer
	}

	return max(
		helper(firstLen, secondLen),
		helper(secondLen, firstLen),
	)
}

The Go implementation follows the same logic as the Python version. Since Go does not provide built-in helper functions like max, a small utility function is defined manually.

Slices are used for the prefix sum array, and all computations use standard integers. Integer overflow is not a concern because the maximum possible sum is well within Go's integer range:

1000 elements × 1000 value = 1,000,000

Unlike Python, Go requires explicit variable declarations and function literals for helper functions.

Worked Examples

Example 1

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

We evaluate:

helper(1, 2)

Prefix sums:

Index	Prefix Sum
0	0
1	0
2	6
3	11
4	13
5	15
6	20
7	21
8	30
9	34

Now scan the right window.

rightStart	Best Left Window	Right Window	Total
1	[0] = 0	[6,5] = 11	11
2	[6] = 6	[5,2] = 7	13
3	[6] = 6	[2,2] = 4	10
4	[6] = 6	[2,5] = 7	13
5	[6] = 6	[5,1] = 6	12
6	[6] = 6	[1,9] = 10	16
7	[9] = 9	[9,4] = 13	22

We also evaluate the reverse ordering and obtain the final answer:

The best arrangement is:

[6,5] + [9]

Example 2

nums = [3,8,1,3,2,1,8,9,0]
firstLen = 3
secondLen = 2

Best arrangement:

[3,8,1] = 12
[8,9] = 17

Total:

Important scan states:

rightStart	Best Left	Right Sum	Combined
3	12	5	17
4	12	3	15
5	12	9	21
6	12	17	29

Maximum becomes 29.

Example 3

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

Best windows:

[5,6,0,9] = 20
[0,3,8] = 11

Total:

Key iterations:

rightStart	Best Left	Right Sum	Combined
4	14	14	28
5	20	14	34
6	20	8	28
7	20	11	31

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each helper performs a single linear scan
Space	O(n)	Prefix sum array stores cumulative sums

The algorithm performs two linear passes over the array, one for each ordering of the windows. Every window sum computation is constant time because of prefix sums. Therefore, total runtime remains linear.

The only extra memory used is the prefix sum array of size n + 1.

Test Cases

from typing import List

s = Solution()

# Provided examples
assert s.maxSumTwoNoOverlap(
    [0,6,5,2,2,5,1,9,4],
    1,
    2
) == 20  # example 1

assert s.maxSumTwoNoOverlap(
    [3,8,1,3,2,1,8,9,0],
    3,
    2
) == 29  # example 2

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

# Minimum valid sizes
assert s.maxSumTwoNoOverlap(
    [1,2],
    1,
    1
) == 3  # only possible arrangement

# Windows touching each other
assert s.maxSumTwoNoOverlap(
    [1,2,3,4,5],
    2,
    2
) == 14  # [2,3] + [4,5]

# Optimal arrangement requires reversing order
assert s.maxSumTwoNoOverlap(
    [10,1,1,1,20],
    1,
    3
) == 32  # [20] + [1,1,10]

# All zeros
assert s.maxSumTwoNoOverlap(
    [0,0,0,0],
    1,
    2
) == 0  # no positive sums

# Entire array used
assert s.maxSumTwoNoOverlap(
    [5,5,5,5],
    2,
    2
) == 20  # both windows consume whole array

# Large values
assert s.maxSumTwoNoOverlap(
    [1000] * 1000,
    500,
    500
) == 1000000  # stress test with maximum values

# Repeated equal windows
assert s.maxSumTwoNoOverlap(
    [4,4,4,4,4,4],
    2,
    2
) == 16  # multiple optimal placements

Test Summary

Test	Why
Example 1	Validates basic functionality
Example 2	Confirms larger left window handling
Example 3	Confirms larger mixed windows
`[1,2]`	Smallest valid input
Touching windows	Ensures adjacent windows are allowed
Reverse ordering	Ensures both orderings are checked
All zeros	Handles no-gain arrays correctly
Entire array used	Verifies exact partitioning
Large uniform array	Stress test for performance
Repeated equal windows	Handles multiple optimal answers

Edge Cases

One important edge case occurs when the two subarrays exactly consume the entire array. In this situation, there is only one possible partitioning of the array. A buggy implementation might incorrectly skip valid touching windows or accidentally require extra spacing between subarrays. This implementation handles the case correctly because it only forbids overlapping, not adjacency.

Another important case is when the optimal ordering is reversed. Many incorrect solutions assume the firstLen window must always appear before the secondLen window. The problem explicitly allows either ordering. This implementation solves the issue by running the helper function twice, once for each possible arrangement.

Arrays containing all zeros are another subtle case. Some algorithms incorrectly initialize tracking variables in ways that assume positive sums exist. Since this solution initializes the best values safely and uses valid window sums throughout, it correctly returns zero when every possible subarray sum is zero.

A further edge case involves windows positioned directly next to each other. Since contiguous windows are valid as long as they do not overlap, the implementation carefully computes boundaries so that:

left_end < right_start

Touching boundaries are allowed naturally, preventing off-by-one mistakes.