# LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to choose three non-overlapping subarrays, each with length `k`, so that their total sum is as large as possible.

Return the starting indices of those three subarrays.

If there are multiple answers with the same total sum, return the lexicographically smallest list of indices. The official statement asks for three non-overlapping length-`k` subarrays with maximum total sum and 0-indexed starting positions.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums`, an integer array, and integer `k` |
| Output | Three starting indices |
| Subarray length | Exactly `k` |
| Overlap rule | The three chosen subarrays cannot overlap |
| Tie rule | Return the lexicographically smallest answer |

Example function shape:

```python
def maxSumOfThreeSubarrays(nums: list[int], k: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
```

All chosen subarrays must have length `2`.

The best choice is:

| Start | Subarray | Sum |
|---:|---|---:|
| `0` | `[1, 2]` | `3` |
| `3` | `[2, 6]` | `8` |
| `5` | `[7, 5]` | `12` |

Total:

```text
3 + 8 + 12 = 23
```

Answer:

```python
[0, 3, 5]
```

Example 2:

```python
nums = [1, 2, 1, 2, 1, 2, 1, 2, 1]
k = 2
```

Many length-`2` windows have the same sum.

The lexicographically smallest valid answer is:

```python
[0, 2, 4]
```

## First Thought: Try All Triples

A direct approach is to compute every possible length-`k` subarray sum.

Then try every triple of starting indices:

```text
i, j, l
```

where:

```text
i + k <= j
j + k <= l
```

For each triple, compute the total sum and keep the best one.

This works, but there can be `O(n)` possible windows, and trying all triples costs:

```text
O(n^3)
```

That is too slow.

We need to reuse the best left and right choices for each possible middle subarray.

## Key Insight

Fix the middle subarray.

If the middle subarray starts at index `mid`, then:

| Part | Valid range |
|---|---|
| Left subarray | Must start at or before `mid - k` |
| Middle subarray | Starts at `mid` |
| Right subarray | Must start at or after `mid + k` |

So for each possible middle index, we need:

1. the best length-`k` window on the left,
2. the middle window,
3. the best length-`k` window on the right.

We can precompute the best left window for every position and the best right window for every position.

## Window Sums

First, compute all length-`k` subarray sums.

Let:

```text
window_sum[i]
```

be the sum of:

```text
nums[i] + nums[i + 1] + ... + nums[i + k - 1]
```

For:

```python
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
```

we get:

| Start | Subarray | Sum |
|---:|---|---:|
| `0` | `[1, 2]` | `3` |
| `1` | `[2, 1]` | `3` |
| `2` | `[1, 2]` | `3` |
| `3` | `[2, 6]` | `8` |
| `4` | `[6, 7]` | `13` |
| `5` | `[7, 5]` | `12` |
| `6` | `[5, 1]` | `6` |

## Best Left Array

Create:

```text
left_best[i]
```

where `left_best[i]` is the starting index of the best window among starts `0` through `i`.

For ties, keep the earlier index to preserve lexicographic order.

That means we update only when the new sum is strictly greater.

```python
if window_sum[i] > window_sum[best]:
    best = i
```

## Best Right Array

Create:

```text
right_best[i]
```

where `right_best[i]` is the starting index of the best window among starts `i` through the end.

For ties, keep the earlier index.

Since we scan from right to left, keeping the earlier index means we update when the new sum is greater than or equal to the current best.

```python
if window_sum[i] >= window_sum[best]:
    best = i
```

The `>=` is important.

When scanning right to left, index `i` is earlier than `best`. If both have the same sum, choosing `i` gives a lexicographically smaller answer.

## Algorithm

1. Compute all length-`k` window sums.
2. Build `left_best`.
3. Build `right_best`.
4. Try every possible middle start `mid`:
   - `mid` ranges from `k` to `len(window_sum) - k - 1`
   - left start is `left_best[mid - k]`
   - right start is `right_best[mid + k]`
5. Compute total:
   ```python id="2j4qm8"
   window_sum[left] + window_sum[mid] + window_sum[right]
   ```
6. If the total is greater than the best total, update the answer.
7. Return the answer.

We update only on strictly greater total. Since we scan `mid` from left to right and the helper arrays already choose earliest ties, this preserves the lexicographically smallest answer.

## Walkthrough

Consider:

```python
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
```

Window sums:

```python
window_sum = [3, 3, 3, 8, 13, 12, 6]
```

Best left indices:

| i | Best start from `0..i` |
|---:|---:|
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 3 |
| 4 | 4 |
| 5 | 4 |
| 6 | 4 |

Best right indices:

| i | Best start from `i..end` |
|---:|---:|
| 0 | 4 |
| 1 | 4 |
| 2 | 4 |
| 3 | 4 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |

Now try middle starts.

For `mid = 2`:

| Part | Start | Sum |
|---|---:|---:|
| Left | `left_best[0] = 0` | `3` |
| Middle | `2` | `3` |
| Right | `right_best[4] = 4` | `13` |

Total:

```text
19
```

For `mid = 3`:

| Part | Start | Sum |
|---|---:|---:|
| Left | `left_best[1] = 0` | `3` |
| Middle | `3` | `8` |
| Right | `right_best[5] = 5` | `12` |

Total:

```text
23
```

This is best, so the answer is:

```python
[0, 3, 5]
```

## Correctness

Every valid answer has some middle subarray. Let its start be `mid`.

Because the three subarrays do not overlap, the left subarray must start at or before `mid - k`, and the right subarray must start at or after `mid + k`.

For this fixed `mid`, the best possible left subarray is exactly `left_best[mid - k]`, because that array stores the maximum-sum valid left window in the allowed range.

The best possible right subarray is exactly `right_best[mid + k]`, because that array stores the maximum-sum valid right window in the allowed range.

Therefore, for each fixed middle index, the algorithm computes the best possible triple using that middle index.

The loop tries every possible middle index, so it considers the best triple for every possible middle subarray.

The maximum over those candidates is therefore the maximum total sum over all valid triples.

For ties, `left_best` keeps the earliest left index, `right_best` keeps the earliest right index, and the middle index is scanned from left to right. The answer is updated only when the total sum is strictly greater. Thus, once a maximum-sum triple is found, a later equal-sum triple does not replace its lexicographically smaller indices.

Therefore, the algorithm returns the lexicographically smallest maximum-sum triple.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each array is computed with one linear scan |
| Space | `O(n)` | We store window sums, left best indices, and right best indices |

## Implementation

```python
class Solution:
    def maxSumOfThreeSubarrays(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        window_count = n - k + 1

        window_sum = [0] * window_count

        current = 0
        for i, value in enumerate(nums):
            current += value

            if i >= k:
                current -= nums[i - k]

            if i >= k - 1:
                window_sum[i - k + 1] = current

        left_best = [0] * window_count
        best = 0

        for i in range(window_count):
            if window_sum[i] > window_sum[best]:
                best = i

            left_best[i] = best

        right_best = [0] * window_count
        best = window_count - 1

        for i in range(window_count - 1, -1, -1):
            if window_sum[i] >= window_sum[best]:
                best = i

            right_best[i] = best

        answer = [-1, -1, -1]
        best_total = -1

        for mid in range(k, window_count - k):
            left = left_best[mid - k]
            right = right_best[mid + k]

            total = (
                window_sum[left]
                + window_sum[mid]
                + window_sum[right]
            )

            if total > best_total:
                best_total = total
                answer = [left, mid, right]

        return answer
```

## Code Explanation

First, we compute all length-`k` window sums:

```python
window_count = n - k + 1
window_sum = [0] * window_count
```

The sliding sum adds the current value:

```python
current += value
```

Once the window is too large, it removes the value that fell out:

```python
if i >= k:
    current -= nums[i - k]
```

When the first complete window exists, we store its sum:

```python
if i >= k - 1:
    window_sum[i - k + 1] = current
```

Next, `left_best[i]` stores the best window start from `0` through `i`.

```python
if window_sum[i] > window_sum[best]:
    best = i
```

We use strict `>` so equal sums keep the earlier index.

Then, `right_best[i]` stores the best window start from `i` through the end.

```python
if window_sum[i] >= window_sum[best]:
    best = i
```

We use `>=` because we are scanning right to left. On equal sums, the current index `i` is earlier.

Finally, we try every possible middle window:

```python
for mid in range(k, window_count - k):
```

The left window must end before `mid`, so it can start no later than `mid - k`.

The right window must start after the middle window, so it starts at least `mid + k`.

```python
left = left_best[mid - k]
right = right_best[mid + k]
```

If the total is better, update the answer:

```python
if total > best_total:
    best_total = total
    answer = [left, mid, right]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSumOfThreeSubarrays(
        [1, 2, 1, 2, 6, 7, 5, 1],
        2,
    ) == [0, 3, 5]

    assert s.maxSumOfThreeSubarrays(
        [1, 2, 1, 2, 1, 2, 1, 2, 1],
        2,
    ) == [0, 2, 4]

    assert s.maxSumOfThreeSubarrays(
        [4, 5, 10, 6, 11, 17, 4, 11, 1, 3],
        1,
    ) == [4, 5, 7]

    assert s.maxSumOfThreeSubarrays(
        [1, 1, 1, 1, 1, 1],
        2,
    ) == [0, 2, 4]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `[1,2,1,2,6,7,5,1]`, `k = 2` | `[0,3,5]` | Standard example |
| Repeated `[1,2]` pattern | `[0,2,4]` | Tie must choose lexicographically smallest |
| `k = 1` case | `[4,5,7]` | Chooses three largest non-overlapping single elements |
| All equal values | `[0,2,4]` | Tie behavior must stay earliest |