LESSON 210 OF 338 · PARTIAL SUMS #1

Max Sum of Three Subarrays in Go: O(n^6) Brute Force

Practice O(n⁶) Read the full explanation

Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Return the total sum of the three subarrays

Example:

Input: [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]
Output: 28
Explanation: Subarrays [2, 3], [7, -2, 9] and [7, -2, 4]
             have the maximum sum of 28

Note:

Subarrays must be non-empty
nums contains at least three numbers

STEP 1 OF 17

Guided

Ctrl + Enter to check

GO · PARTIAL SUMS #1

Max Sum Of Three Subarrays in Go, explained

Problem overview

The function maxSumOfThreeSubarrays receives a slice of integers, nums, with at least three elements. It must choose three non-empty, non-overlapping subarrays (contiguous blocks), and return the largest possible total of their sums. The values can be negative.

For nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4], the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], with sums 5, 14 and 9. The total is 28.

Approach: try every triple of subarrays

This first lesson on the problem is the brute force, and it exists to make the structure clear before faster versions replace it. A subarray is fixed by its first and last index. Three non-overlapping subarrays, in left-to-right order, are fixed by six indices:

i1 <= j1 < i2 <= j2 < i3 <= j3

The first subarray runs from i1 to j1, the second from i2 to j2, and the third from i3 to j3. Each later subarray must start strictly after the previous one ends, which is what makes them non-overlapping. Because the sum is symmetric, considering only this left-to-right order loses nothing: any three disjoint subarrays can be listed from left to right.

The approach is six nested loops, one per index. Running sums keep each loop cheap: when j1 moves one step right, sum1 just adds nums[j1], instead of re-adding the whole subarray.

The number of index combinations grows like n to the sixth power. For n = 10 the loops reach the innermost statement 1,716 times, and for a few hundred elements this approach is already far too slow. That is the motivation for the faster lessons on this problem.

Step by step

Store the length in n := len(nums), since every loop bound uses it.
Create maxSum with a very negative start. It can't start at 0, because the true answer may be negative, as in [-5, -1, -3], which has the answer -9. The value -1 << 62, about -4.6 x 10^18, is smaller than any realistic sum and still fits in a 64-bit int.
Loop over i1 from 0 to n - 1: the first element of the first subarray.
Declare sum1 := 0 inside that loop. It is the sum of the first subarray, and it restarts for every i1.
Loop over j1 from i1, the last element of the first subarray. Starting at i1 keeps the subarray non-empty.
Extend the sum: sum1 += nums[j1], inside the j1 loop.
Loop over i2 from j1 + 1. The second subarray has to start after the first ends.
Declare sum2 := 0 inside the i2 loop.
Loop over j2 from i2.
Extend: sum2 += nums[j2].
Loop over i3 from j2 + 1.
Declare sum3 := 0 inside the i3 loop.
Loop over j3 from i3.
Extend: sum3 += nums[j3].
Compare the total. Right after sum3 is updated, test whether sum1+sum2+sum3 is greater than maxSum.
Record it. Inside that if, set maxSum to the total.
Return maxSum after the outermost loop ends.

The solution in Go

func maxSumOfThreeSubarrays(nums []int) int {
    n := len(nums)
    maxSum := -1 << 62
    for i1 := 0; i1 < n; i1++ {
        sum1 := 0
        for j1 := i1; j1 < n; j1++ {
            sum1 += nums[j1]
            for i2 := j1 + 1; i2 < n; i2++ {
                sum2 := 0
                for j2 := i2; j2 < n; j2++ {
                    sum2 += nums[j2]
                    for i3 := j2 + 1; i3 < n; i3++ {
                        sum3 := 0
                        for j3 := i3; j3 < n; j3++ {
                            sum3 += nums[j3]
                            if sum1+sum2+sum3 > maxSum {
                                maxSum = sum1 + sum2 + sum3
                            }
                        }
                    }
                }
            }
        }
    }
    return maxSum
}

Go details:

-1 << 62 is a constant expression. In maxSum := -1 << 62 it takes the type int, and on a 64-bit platform it equals -4611686018427387904.
Each sumK is declared with := inside the loop whose index it belongs to, so it is a fresh zero for each new start index. Declaring it outside would carry the old total over.
Go's if needs no parentheses around the condition, but the braces are required.
The condition is written as sum1+sum2+sum3 > maxSum. The built-in max (Go 1.21 and later) could replace the if, but the explicit comparison works with every version.

Complexity

Time: O(n^6). Six nested loops, each running over up to n positions, with constant work in the innermost body. Only some index combinations are valid, because each loop starts after the previous one, but they still grow as a constant times n^6.

Space: O(1). Only scalar variables are used.

Edge cases and common mistakes

Exactly three elements. [1, 2, 3] has only one choice, one element each, and returns 6.
All values negative. [-1, -2, -3, -4] returns -6, from three single elements, because every subarray must be non-empty. A maxSum that starts at 0 would wrongly return 0.
Overlap. Starting i2 at j1 instead of j1 + 1 lets two subarrays share an element, which counts that element twice.
Empty subarrays. The inner loops must start at the start index and not after it, otherwise a subarray could have no elements.
Too few elements. With fewer than three, no triple exists and the function would return the starting value of maxSum. The problem guarantees at least three.
Using it on large inputs. The loops are fine for a dozen elements. For larger slices, the run time explodes, which is the reason to look for the faster versions.

Try in the editor above: the example should give 28, [1, 2, 3, 4, 5, 6] should give 21 and [4, -10, 4, -10, 4] should give 12.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free