LESSON 220 OF 338 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Go: O(n) with a Running Best Difference

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 21

Guided

Ctrl + Enter to check

GO · PARTIAL SUMS #2

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 chooses three non-empty, non-overlapping subarrays, one after another, and returns the largest possible total of their sums. Values may 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 answer is 28.

Approach: remove the loop over the middle's start

The quadratic solution fixes the middle subarray and looks up the best first subarray on its left and the best third on its right. It still loops over both ends of the middle. This lesson keeps the same two tables, leftMaxSum and rightMaxSum, but loops only over where the middle ends.

The trick uses prefix sums. Let P(i) be the sum of nums[0..i]. If the middle runs from k to i, its sum is P(i) - P(k-1). The best first subarray before it is worth leftMaxSum[k-1]. So the first and middle parts together are worth P(i) + (leftMaxSum[k-1] - P(k-1)). For a fixed i only the bracket depends on k, so keep its best value so far, maxDiff, while i moves right. Adding rightMaxSum[i+1] for the third subarray finishes each candidate in constant time.

Step by step

Store n, and build leftMaxSum with make([]int, n). Seed leftMaxSum[0] with nums[0].
Track the best run ending at each index in maxSum, starting at nums[0]. For each i from 1, set maxSum = nums[i] + max(maxSum, 0) and leftMaxSum[i] = max(leftMaxSum[i-1], maxSum).
Build rightMaxSum the same way from the right: seed the last entry with nums[n-1], reuse maxSum from nums[n-1], and loop from n - 2 down to 0.
Reset maxSum to -(1 << 31) as the best answer so far, lower than any total.
Declare partialSum as nums[0]. At the start of each iteration it holds the sum of nums[0..i-1].
Declare maxDiff as -(1 << 31). It holds the largest leftMaxSum[k-1] minus the sum of nums[0..k-1] over all middle starts k seen so far.
Loop over the middle's last index i from 1 to n - 2, leaving room for a first subarray before it and a third one after it.
Add the option of starting the middle at i: maxDiff = max(leftMaxSum[i-1]-partialSum, maxDiff), while partialSum is still the sum up to i-1.
Add nums[i] to partialSum, which now covers nums[0..i].
Score the candidate as partialSum + rightMaxSum[i+1] + maxDiff and keep the larger of it and maxSum.
Return maxSum.

The solution in Go

type Solution struct{}

func maxSumOfThreeSubarrays(nums []int) int {
    n := len(nums)

    leftMaxSum := make([]int, n)
    leftMaxSum[0] = nums[0]
    maxSum := nums[0]
    for i := 1; i < n; i++ {
        maxSum = nums[i] + max(maxSum, 0)
        leftMaxSum[i] = max(leftMaxSum[i-1], maxSum)
    }

    rightMaxSum := make([]int, n)
    rightMaxSum[n-1] = nums[n-1]
    maxSum = nums[n-1]
    for i := n - 2; i >= 0; i-- {
        maxSum = nums[i] + max(maxSum, 0)
        rightMaxSum[i] = max(rightMaxSum[i+1], maxSum)
    }

    maxSum = -(1 << 31)
    partialSum := nums[0]
    maxDiff := -(1 << 31)
    for i := 1; i < n-1; i++ {
        maxDiff = max(leftMaxSum[i-1]-partialSum, maxDiff)
        partialSum += nums[i]
        maxSum = max(partialSum+rightMaxSum[i+1]+maxDiff, maxSum)
    }

    return maxSum
}

func (this Solution) maxSumOfThreeSubarrays(nums []int) int {
    return maxSumOfThreeSubarrays(nums)
}

Go details:

A function and a method with the same name. The package-level function maxSumOfThreeSubarrays and the method of Solution with the same name live in different namespaces, so they don't clash. Inside the method, the bare name maxSumOfThreeSubarrays(nums) refers to the package-level function, so the method simply forwards to it. It is not recursion.
Built-in max. Go 1.21 and later have max and min built in, so no helper is required.
Reassigning with =. maxSum is reused for three jobs. The first declaration uses :=; later lines use =.
Unused names are errors. Go refuses to compile a program with an unused local variable, so every variable here, including partialSum and maxDiff, must be read somewhere.
The sentinel. -(1 << 31) is -2147483648. Totals below that range would not be handled.

Worked example

For the example, leftMaxSum is [2 5 5 7 7 14 14 14 14 14] and rightMaxSum is [14 14 14 14 9 9 9 9 4 4]. At i = 3, maxDiff becomes leftMaxSum[2] - (2 + 3 - 8) = 5 - (-3) = 8, which corresponds to starting the middle at index 3. At i = 5 the partial sum is 11, maxDiff is still 8, and rightMaxSum[6] is 9. The candidate is 11 + 9 + 8 = 28, the answer. The first part, [2, 3], plus the middle [7, -2, 9] is worth 11 + 8 = 19, and the third part adds 9.

Reading the three parts

It helps to name what each term in the final score stands for. partialSum is the total of everything from the start of the slice up to the end of the middle subarray. maxDiff subtracts the prefix before the middle's start and adds the best first subarray there, so the two together equal the best first subarray plus the middle. This only works because the first subarray is always chosen from the elements strictly before the middle, which is exactly what leftMaxSum[k-1] guarantees. The last term, rightMaxSum[i+1], adds the best third subarray strictly after the middle. No pair of parts can overlap, and every valid triple is considered by some pair (k, i).

Complexity

Time: O(n). Each of the three passes does constant work per element.

Space: O(n). The two tables hold n values each. The rest is a few integers.

Edge cases and common mistakes

Exactly three numbers. The loop runs once, at i = 1, and the answer is the sum of all three.
All negative numbers. For [-1, -2, -3] the answer is -6, and for [-5, -1, -7, -2] it is -8. Starting the best answer at 0 would hide this.
Updating maxDiff after adding nums[i]. The difference needs the prefix sum up to i-1, so the order of the two lines matters.
Overlap. The first subarray comes from leftMaxSum[k-1] and the third from rightMaxSum[i+1], so the middle's range separates them.
Loop bounds. Starting at 0 would read leftMaxSum[-1], which panics; ending at n-1 would read rightMaxSum[n], which also panics.

Testing

[2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
[-1, -2, -3] gives -6.
[-5, -1, -7, -2] gives -8.
[1, 2, 3, 4, 5] gives 15.

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

Start learning free