Maximum Sum of 3 Non-Overlapping Subarrays

Maximum Sum of 3 Non-Overlapping Subarrays is a classic prefix-sum plus dynamic-programming problem. The trick is to stop thinking about three windows at once and instead fix the middle window, then ask for the best window on each side.

The slow way first

The brute force tries every triple of non-overlapping windows: pick a left window, a middle window after it, a right window after that, and sum all three. With three nested choices that is roughly O(n³) — far too slow for a large array.

The question to ask: if I commit to the middle window, what do I still need? I need the single best window that fits entirely to its left, and the single best window that fits entirely to its right. If I had those two answers precomputed, each middle choice becomes an O(1) lookup.

The idea: fix the middle, look both ways

First slide a length-k window across the array to get every window sum w[i]. Then build two helper arrays:

• left[i] = the index of the best window in w[0..i] (best so far, scanning left to right).
• right[i] = the index of the best window in w[i..end] (best so far, scanning right to left).

Now loop over every legal middle window m. The best left partner is left[m - k] and the best right partner is right[m + k]. Add the three sums, keep the maximum.

The key insight: left and right turn the two outer windows into instant lookups, so only the middle window needs a loop.

Walk through it

Step through the animation. First the seven window sums appear: [3, 3, 3, 8, 13, 12, 6]. The best left window ends at index 4 (sum 13); the best right window starts at index 5 (sum 12). As the middle window slides, we combine its sum with the best fitting left and right windows. The winning split is left (0,1)=3, middle (4,5)=13, right (6,7)=6, totaling 22.

Pseudocode

w[i] = sum of nums[i .. i+k-1]      # every length-k window sum
left[i]  = index of best window in w[0 .. i]    (scan left to right)
right[i] = index of best window in w[i .. end]  (scan right to left)
best_total = 0
for each middle window m from k to len(w) - k - 1:
    l = left[m - k]                 # best window ending before the middle
    r = right[m + k]                # best window starting after the middle
    total = w[l] + w[m] + w[r]
    if total > best_total:
        best_total = total
        answer = [l, m, r]
return answer

The Python solution

def max_sum_of_three(nums, k):
    n = len(nums)
    w = [0] * (n - k + 1)
    s = sum(nums[:k])
    w[0] = s
    for i in range(1, len(w)):
        s += nums[i + k - 1] - nums[i - 1]
        w[i] = s
    left = [0] * len(w)
    best = 0
    for i in range(len(w)):
        if w[i] > w[best]:
            best = i
        left[i] = best
    right = [0] * len(w)
    best = len(w) - 1
    for i in range(len(w) - 1, -1, -1):
        if w[i] >= w[best]:
            best = i
        right[i] = best
    ans = None
    total = 0
    for m in range(k, len(w) - k):
        l, r = left[m - k], right[m + k]
        cur = w[l] + w[m] + w[r]
        if cur > total:
            total = cur
            ans = [l, m, r]
    return ans

• w holds every length-k window sum, built in O(n) with a sliding sum (s += new - old).
• left[i] records the index of the best window at or before i. We use > so ties keep the earliest index — that gives the lexicographically smallest answer.
• right[i] records the best window at or after i. We use >= so ties prefer the earliest index when scanning backward.
• The final loop fixes the middle window m and reads left[m - k] and right[m + k] in O(1).
• We keep the triple with the largest combined sum.

Complexity

We trade O(n) extra space for the window-sum and helper arrays to collapse the cubic search into three linear scans.

When this pattern shows up

Practice