Maximum Sum of 3 Non-Overlapping Subarrays [Hard] — Sliding Window + DP

Problem Statement#

LeetCode 689 — Maximum Sum of 3 Non-Overlapping Subarrays (Hard)

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k that have the maximum total sum. Return their starting indices as a list. If there are multiple answers with the same total sum, return the lexicographically smallest one.

Constraints:

• 1 <= nums.length <= 20000
• 1 <= nums[i] < 65536
• 1 <= k <= floor(nums.length / 3)

Example 1:

Input:  nums = [1, 2, 1, 2, 6, 7, 5, 1],  k = 2
Output: [0, 3, 5]
Explanation:
  Window at index 0: [1, 2]  → sum = 3
  Window at index 3: [2, 6]  → sum = 8
  Window at index 5: [7, 5]  → sum = 12
  Total = 23 (maximum possible)

Example 2:

Input:  nums = [1, 2, 1, 2, 1, 2, 1, 2, 1],  k = 2
Output: [0, 2, 4]
Explanation: Multiple valid answers exist; [0, 2, 4] is lexicographically smallest.

Why This Problem Matters#

This problem appears in Google, Facebook, and Microsoft on-site rounds and is a canonical example of combining two techniques that individually feel simple but together require careful thought:

1. Sliding window sums — precompute in O(n) the sum of every contiguous window of size k.
2. Left/Right DP prefix/suffix scans — for every candidate middle window, instantly know the best window to its left and the best window to its right.

The reason interviewers love it is that the naive O(n³) brute force is obvious, but getting to O(n) requires the insight that the three windows are independent once you fix the middle one. That insight — fix the middle, precompute the best left and best right — generalizes to a family of problems involving non-overlapping intervals.

The lexicographically smallest constraint adds an extra layer: you must be careful about whether you use strict > or >= when updating your best-seen trackers. Getting this wrong produces correct sums but wrong indices — exactly the kind of subtle bug that separates strong from average candidates.

The Sliding Window + Left/Right DP Insight#

Step 1 — Precompute All Window Sums#

A window sum starting at index i is nums[i] + nums[i+1] + ... + nums[i+k-1]. Computing all of them naively costs O(nk). Instead, slide the window:

sums[0] = nums[0] + ... + nums[k-1]
sums[i] = sums[i-1] - nums[i-1] + nums[i+k-1]   (for i >= 1)

This gives an array sums of length m = n - k + 1 in O(n) time. sums[i] is the sum of the window starting at index i.

Step 2 — Build the left Array#

left[i] = the index j in [0 .. i] such that sums[j] is maximized (ties broken in favor of the smaller index, i.e., the leftmost).

We scan left to right, tracking the best index seen so far:

best = 0
for i in 0 .. m-1:
    if sums[i] > sums[best]:   # strict > keeps leftmost on ties
        best = i
    left[i] = best

Step 3 — Build the right Array#

right[i] = the index j in [i .. m-1] such that sums[j] is maximized (ties broken in favor of the smaller index, i.e., leftmost again).

We scan right to left:

best = m - 1
for i in m-1 .. 0:
    if sums[i] >= sums[best]:  # >= keeps leftmost on ties (scanning right-to-left, >= updates earlier index)
        best = i
    right[i] = best

Why >= here and > in the left scan? Because we scan right-to-left: when we encounter index i where sums[i] == sums[best], index i is smaller (leftmost), so we want to prefer it — hence >=.

Step 4 — Enumerate the Middle Window#

The middle window can start at any index mid such that:

• There is room for a full left window: mid >= k (so left window can start at mid - k)
• There is room for a full right window: mid <= m - k - 1 (so right window can start at mid + k)

For each valid mid:

l = left[mid - k]    # best left window index
r = right[mid + k]   # best right window index
total = sums[l] + sums[mid] + sums[r]

Track the maximum total and record [l, mid, r] when a new maximum is found (strict > to keep the lexicographically smallest triple).

All four steps are O(n), so the overall algorithm is O(n) time and O(n) space.

Visual Dry Run#

Let us trace nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2.

Step 1: Compute window sums (m = 8 - 2 + 1 = 7)

index:  0  1  2  3  4  5  6
nums:  [1, 2, 1, 2, 6, 7, 5, 1]
 
sums[0] = 1+2 = 3
sums[1] = 3 - 1 + 1 = 3
sums[2] = 3 - 2 + 2 = 3
sums[3] = 3 - 1 + 6 = 8
sums[4] = 8 - 2 + 7 = 13
sums[5] = 13 - 6 + 5 = 12
sums[6] = 12 - 7 + 1 = 6
 
sums = [3, 3, 3, 8, 13, 12, 6]

Step 2: Build left array (scan left to right, strict >)

i=0: sums[0]=3 > sums[0]=3? No  → left[0]=0,  best=0
i=1: sums[1]=3 > sums[0]=3? No  → left[1]=0,  best=0
i=2: sums[2]=3 > sums[0]=3? No  → left[2]=0,  best=0
i=3: sums[3]=8 > sums[0]=3? Yes → best=3; left[3]=3
i=4: sums[4]=13> sums[3]=8? Yes → best=4; left[4]=4
i=5: sums[5]=12> sums[4]=13?No  → left[5]=4,  best=4
i=6: sums[6]=6 > sums[4]=13?No  → left[6]=4,  best=4
 
left = [0, 0, 0, 3, 4, 4, 4]

Step 3: Build right array (scan right to left, >=)

i=6: sums[6]=6 >=sums[6]=6?Yes → best=6; right[6]=6
i=5: sums[5]=12>=sums[6]=6? Yes → best=5; right[5]=5
i=4: sums[4]=13>=sums[5]=12?Yes → best=4; right[4]=4
i=3: sums[3]=8 >=sums[4]=13?No  → right[3]=4,  best=4
i=2: sums[2]=3 >=sums[4]=13?No  → right[2]=4,  best=4
i=1: sums[1]=3 >=sums[4]=13?No  → right[1]=4,  best=4
i=0: sums[0]=3 >=sums[4]=13?No  → right[0]=4,  best=4
 
right = [4, 4, 4, 4, 4, 5, 6]

Step 4: Enumerate middle window

Valid mid range: mid >= k=2 and mid <= m-k-1 = 7-2-1 = 4, so mid in the set 2, 3, 4.

mid=2: l=left[2-2]=left[0]=0,  r=right[2+2]=right[4]=4
       total = sums[0]+sums[2]+sums[4] = 3+3+13 = 19
       19 > 0 → ans=[0,2,4], best_sum=19
 
mid=3: l=left[3-2]=left[1]=0,  r=right[3+2]=right[5]=5
       total = sums[0]+sums[3]+sums[5] = 3+8+12 = 23
       23 > 19 → ans=[0,3,5], best_sum=23
 
mid=4: l=left[4-2]=left[2]=0,  r=right[4+2]=right[6]=6
       total = sums[0]+sums[4]+sums[6] = 3+13+6 = 22
       22 > 23? No
 
Final answer: [0, 3, 5]

The three windows are nums[0..1]=[1,2], nums[3..4]=[2,6], nums[5..6]=[7,5] with total sum 23.

Common Mistakes#

1. Using >= vs > in the wrong scan direction#

The most frequent mistake is using the same comparison operator (> or >=) for both the left and right scans.

• Left scan (left to right): use strict >. When sums[i] == sums[best], keep the smaller (earlier) index, so do NOT update.
• Right scan (right to left): use >=. When sums[i] == sums[best], index i is smaller than best (since we scan backward), so update to get the leftmost.

Swapping these produces wrong indices on tie-breaking test cases even though the sum is correct.

2. Wrong bounds for the middle window loop#

A common off-by-one: iterating mid from k to m - k inclusive (using range(k, m - k + 1) in Python). The right window starts at mid + k, which must be a valid index in sums, i.e., mid + k <= m - 1, meaning mid <= m - k - 1. The correct Python range is range(k, m - k).

3. Forgetting that sums indices and nums indices are the same#

sums[i] is the sum of the window starting at nums[i]. So the answer [l, mid, r] already contains the correct starting indices into nums — no adjustment needed. A common mistake is adding or subtracting k to convert, which is wrong.

4. Recomputing window sums on the fly in O(k) each time#

Some candidates skip the precomputation step and compute sum(nums[mid:mid+k]) inside the loop. This inflates the time complexity from O(n) to O(nk). For n = 20000 and large k, this is significantly slower and will TLE.

5. Not initializing ans to [-1, -1, -1]#

The problem guarantees an answer always exists given the constraints, but initializing ans to [0, 0, 0] can mask bugs during testing because the initial state looks like a valid answer.

Solutions#

Python#

from typing import List
 
def maxSumOfThreeSubarrays(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    m = n - k + 1  # number of valid starting indices for a window of size k
 
    # --- Step 1: Precompute all window sums using sliding window ---
    sums = [0] * m
    sums[0] = sum(nums[:k])                         # seed: sum of first window
    for i in range(1, m):
        # slide: remove leftmost element, add new rightmost element
        sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1]
 
    # --- Step 2: left[i] = index of best window sum in sums[0..i] ---
    # Ties broken by keeping the smaller (leftmost) index → strict >
    left = [0] * m
    best = 0
    for i in range(m):
        if sums[i] > sums[best]:  # strictly greater → leftmost wins on tie
            best = i
        left[i] = best
 
    # --- Step 3: right[i] = index of best window sum in sums[i..m-1] ---
    # Scan right-to-left; >= keeps the leftmost index when sums are equal
    right = [0] * m
    best = m - 1
    for i in range(m - 1, -1, -1):
        if sums[i] >= sums[best]:  # >= because leftward index is smaller
            best = i
        right[i] = best
 
    # --- Step 4: Enumerate valid middle windows ---
    # Middle starts at mid; left window ends before mid (starts at mid-k),
    # right window starts right after middle ends (starts at mid+k).
    ans = [-1, -1, -1]
    best_sum = 0
    for mid in range(k, m - k):        # mid in [k, m-k-1] inclusive
        l = left[mid - k]              # best left window index
        r = right[mid + k]             # best right window index
        total = sums[l] + sums[mid] + sums[r]
        if total > best_sum:           # strict > keeps lexicographically smallest
            best_sum = total
            ans = [l, mid, r]
 
    return ans

JavaScript#

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSumOfThreeSubarrays(nums, k) {
    const n = nums.length;
    const m = n - k + 1; // number of valid window starting positions
 
    // --- Step 1: Precompute all window sums ---
    const sums = new Array(m).fill(0);
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += nums[i]; // seed first window
    sums[0] = windowSum;
    for (let i = 1; i < m; i++) {
        // slide: subtract element leaving window, add element entering window
        sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1];
    }
 
    // --- Step 2: left[i] = best window index in sums[0..i] ---
    // Use strict > so ties keep the leftmost (lexicographically smaller) index
    const left = new Array(m).fill(0);
    let best = 0;
    for (let i = 0; i < m; i++) {
        if (sums[i] > sums[best]) best = i; // strictly greater → leftmost wins
        left[i] = best;
    }
 
    // --- Step 3: right[i] = best window index in sums[i..m-1] ---
    // Scan right-to-left; >= updates to smaller index when sums are equal
    const right = new Array(m).fill(0);
    best = m - 1;
    for (let i = m - 1; i >= 0; i--) {
        if (sums[i] >= sums[best]) best = i; // >= keeps leftmost on tie
        right[i] = best;
    }
 
    // --- Step 4: Enumerate all valid middle windows ---
    let ans = [-1, -1, -1];
    let bestSum = 0;
    for (let mid = k; mid < m - k; mid++) { // mid in [k, m-k-1]
        const l = left[mid - k];             // best left window start index
        const r = right[mid + k];            // best right window start index
        const total = sums[l] + sums[mid] + sums[r];
        if (total > bestSum) {               // strict > keeps lex smallest triple
            bestSum = total;
            ans = [l, mid, r];
        }
    }
 
    return ans;
}

Complexity Analysis#

The space can technically be reduced to O(1) extra (beyond the output) using an alternative one-pass sliding approach that maintains running best-left and best-two-left as the right window advances, but the array-based approach above is far easier to reason about in an interview and is already optimal in time.

Follow-up Questions#

1. Generalize to k non-overlapping windows#

Interviewers often ask: "What if instead of exactly 3 windows you need exactly t windows?"

The left/right DP approach does not extend cleanly beyond 3 without exploding in complexity. The natural generalization uses a 2D DP table: dp[i][j] = maximum sum using i windows chosen from the first j valid window positions. This runs in O(t * n) time and O(t * n) space, which is acceptable when t is small.

# Generalized: find t non-overlapping windows of size k
def maxSumOfTSubarrays(nums, k, t):
    n = len(nums)
    m = n - k + 1
    # Build window sums
    sums = [sum(nums[:k])]
    for i in range(1, m):
        sums.append(sums[-1] - nums[i - 1] + nums[i + k - 1])
    # dp[i][j]: best total sum using i windows from sums[0..j]
    NEG_INF = float('-inf')
    dp = [[NEG_INF] * m for _ in range(t + 1)]
    for j in range(m):
        dp[0][j] = 0  # zero windows → zero sum
    for i in range(1, t + 1):
        running_max = NEG_INF
        for j in range((i - 1) * k, m - (t - i) * k):
            # Can we start window i at position j?
            prev = dp[i - 1][j - k] if j >= k else NEG_INF
            if prev != NEG_INF:
                running_max = max(running_max, prev)
            if running_max != NEG_INF:
                dp[i][j] = running_max + sums[j]
    return max(dp[t])

2. Connection to LC 123 — Best Time to Buy and Sell Stock III#

LC 123 asks for the maximum profit from at most two transactions (buy low, sell high) with no overlap. The structural connection is exact: each "transaction" is a segment of the array where profit is extracted, and segments cannot overlap. LC 123 is solved with a similar left/right DP split — left[i] = max profit from one transaction in [0..i], right[i] = max profit from one transaction in [i..n-1], then combine at every split point.

LC 689 is a natural extension: instead of one-element "buy" and "sell" events, you have fixed-length windows of size k. The core technique — precompute the best independently on each side, then join at a pivot — is identical.

3. What if windows can have different lengths?#

This breaks the uniform window assumption and is substantially harder (closer to interval scheduling maximization). It typically requires dynamic programming with sorted intervals and binary search, running in O(n log n).

This Pattern Solves#

The Sliding Window + Left/Right DP pattern applies whenever you need to:

• Pick a fixed number of non-overlapping fixed-length segments from an array to maximize some aggregate.
• Compute the best independent choices on the left and right of a pivot simultaneously.

Problems that use the same core pattern:

• LC 123 — Best Time to Buy and Sell Stock III (2 transactions)
• LC 188 — Best Time to Buy and Sell Stock IV (k transactions, generalized DP)
• LC 1031 — Maximum Sum of Two Non-Overlapping Subarrays (same technique, 2 windows)
• LC 1477 — Find Two Non-Overlapping Subarrays Each With Target Sum (sliding window + prefix DP)
• LC 2555 — Maximize Win From Two Segments (sliding window + left DP)

Recognizing this family in an interview is the difference between spending 45 minutes on a hard problem and cracking it in 20.

Key Takeaways#

• Fix the middle window to decouple the problem: best left window up to mid-k and best right window from mid+k are now independent and precomputable.
• Precompute window_sum (sliding window of size k), left[i] (best window start up to i), and right[i] (best window start from i) in three O(n) passes.
• The final scan tries every middle start in [k, n-2k] and combines left[mid-k] + window[mid] + right[mid+k] in O(1) per candidate.
• Use strict > (not >=) in the left-to-right left[] pass to preserve the leftmost tie-breaking index.
• Use >= (not >) in the right-to-left right[] pass to prefer smaller indices when sums tie.
• O(n) time, O(n) space; the window sums prefix array avoids recomputing subarray sums.
• This exact pattern (left DP + right DP + middle pivot) solves LC 1031 (2 windows) and LC 123 (2 transactions stock problem).