LESSON 246 OF 442 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Go: Kadane on Both Sides of a Middle

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

Max Sum Of Three Subarrays in Go, explained

Problem overview

The function maxSumOfThreeSubarrays receives a slice nums of integers, with at least three elements, and returns the largest possible total of three non-overlapping, non-empty subarrays. The subarrays are contiguous pieces of nums, and they may leave gaps between them.

For [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, so the answer is 28. The elements -8 and -9 are left out as gaps.

Approach: try every middle, take the best on each side

Choosing three subarrays at once has too many combinations. Fix the middle one instead. If the middle subarray is nums[i..j], the other two must lie entirely before it and entirely after it. The first one can be any subarray of nums[:i], and the best choice is simply the maximum subarray sum in that prefix. The third is the maximum subarray sum in the suffix nums[j+1:]. The total for this middle is then sum1 + sum2 + sum3.

The maximum sum of a subarray in a slice comes from Kadane's algorithm, from the problem Maximum Sum Subarray: scan once and keep the best sum of a subarray ending at the current element. That sum either extends the previous one, if it is positive, or starts fresh at the current value.

The solution tries every middle with two loops. The outer loop picks the start i, and the inner loop extends the end j one element at a time, keeping a running sum for the middle. For each pair it runs Kadane on the prefix once per i and on the suffix once per j. This is simple and correct, but it costs O(n³). Precomputing the best prefix and suffix values would remove a factor, but this version keeps the idea as direct as possible.

Step by step

Store len(nums) in n, since it is used often.
Declare maxSum, the best total so far. The answer can be negative, so it starts at -(1 << 31), the smallest 32-bit integer, instead of 0.
Loop over i from 1 while i < n. This is the first element of the middle subarray. Starting at 1 keeps the first subarray non-empty.
Compute sum1 with maxSumSubarray(nums[:i]), the best subarray before i.
Declare sum2 at 0: the middle subarray is empty until the inner loop adds elements.
Loop over j from i while j < n-1, the last element of the middle subarray. Stopping at n - 2 leaves at least one element for the third subarray.
Add nums[j] to sum2.
Compute sum3 with maxSumSubarray(nums[j+1:]), the best subarray after j.
Update maxSum with max(maxSum, sum1+sum2+sum3).
Return maxSum after the outer loop.
Write maxSumSubarray above it, taking a []int and returning an int: the Kadane scan.
Declare result, the best sum so far, starting at nums[0] and not 0, because all the numbers may be negative.
Declare maxSum, the best sum of a subarray ending at the current element, starting at 0. This is a different variable from the one in the main function.
Loop over the values with range, naming each one val.
Update the running sum: val plus the larger of maxSum and 0.
Update result with the larger of result and maxSum.
Return result.

The solution in Go

func maxSumSubarray(nums []int) int {
    result := nums[0]
    maxSum := 0
    for _, val := range nums {
        maxSum = val + max(maxSum, 0)
        result = max(result, maxSum)
    }
    return result
}

func maxSumOfThreeSubarrays(nums []int) int {
    n := len(nums)
    maxSum := -(1 << 31)
    for i := 1; i < n; i++ {
        sum1 := maxSumSubarray(nums[:i])
        sum2 := 0
        for j := i; j < n-1; j++ {
            sum2 += nums[j]
            sum3 := maxSumSubarray(nums[j+1:])
            maxSum = max(maxSum, sum1+sum2+sum3)
        }
    }
    return maxSum
}

Go details worth a closer look:

Slicing does not copy. nums[:i] and nums[j+1:] are views of the same backing array, so passing them to maxSumSubarray costs nothing extra in memory. The helper only reads them.
Built-in max. Since Go 1.21, max is a built-in function for ordered types, so no math import is needed.
The constant -(1 << 31) is an untyped constant, and := gives maxSum the type int, which is 64 bits here, so the value is -2,147,483,648. The idea is only "below any possible total". A total below that would need numbers of very large magnitude.
Two variables named maxSum. One is local to the helper, the other to maxSumOfThreeSubarrays. They never interact.
The inner loop may not run. When i == n-1, the condition j < n-1 fails at once, so sum3 never receives an empty slice, which would make nums[0] in the helper panic.

Complexity

Time: O(n³). The two loops try O(n²) middles, and every inner step runs maxSumSubarray on a suffix of up to n elements. The prefix scan runs once per outer step and adds only O(n²) in total.

Space: O(1). The slices are views of the input and the helper keeps a few integers.

Edge cases and common mistakes

Exactly three elements. [1, 2, 3] gives 6. Only i = 1, j = 1 is possible, so each subarray is a single element.
All negative. [-1, -2, -3] gives -6 and [-5, -1, -7, -2] gives -8, from -5, -1 and -2. Starting maxSum at 0 would wrongly produce 0, and so would starting the Kadane result at 0.
Gaps are allowed. In [4, -10, 4, -10, 4] the answer is 12: the three 4s with the -10s skipped between them.
Empty subarrays. The loop bounds keep each part non-empty: the prefix has at least one element since i starts at 1, the middle has one since j starts at i, and the suffix has one since j stops at n - 2.
Kadane's reset. Taking val + max(maxSum, 0) drops a negative running sum. Adding it anyway would drag later values down.
Slice bounds. nums[j+1:] is valid even for j + 1 == n and gives an empty slice, but the loop never gets there.

Testing

[2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
[1, 2, 3] gives 6.
[-1, -2, -3] gives -6.
[-5, -1, -7, -2] gives -8.
[4, -10, 4, -10, 4] gives 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