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

Example function shape:

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

Examples

Example 1:

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

All chosen subarrays must have length 2.

The best choice is:

Total:

3 + 8 + 12 = 23

Answer:

[0, 3, 5]

Example 2:

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:

[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:

i, j, l

where:

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:

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:

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:

window_sum[i]

be the sum of:

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

For:

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

we get:

Best Left Array

Create:

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.

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

Best Right Array

Create:

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.

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:

   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:

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

Window sums:

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

Best left indices:

Best right indices:

Now try middle starts.

For mid = 2:

Total:

19

For mid = 3:

Total:

23

This is best, so the answer is:

[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).

Implementation

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:

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

The sliding sum adds the current value:

current += value

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

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

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

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

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

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.

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:

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.

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

If the total is better, update the answer:

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

Testing

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: