# 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

| Item | Meaning |
|---|---|
| Input | Array `nums`, lengths `firstLen` and `secondLen` |
| Output | Maximum combined sum of two non-overlapping subarrays |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear passes |
| Space | `O(n)` | Prefix sums |

## 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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `firstLen=1, secondLen=2` | `20` | `[9]` + `[6,5]` |
| `firstLen=3, secondLen=2` | `29` | `[3,8,1]` or `[8,9,0]` combined optimally |
| `firstLen=4, secondLen=3` | `31` | Best two non-overlapping windows |