Start learning free

LESSON 219 OF 338 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Go: Prefix and Suffix Maximums, O(n²)

Practice O(n2) 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 22
    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 must choose three non-empty, non-overlapping subarrays, placed one after another, and return the largest possible total of their sums. 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, so the answer is 28.

    Approach: fix the middle, look up the sides

    Choosing all three subarrays at once is too many combinations. The key idea is to fix the middle subarray and let the two outer ones take care of themselves. For a given middle range, the best first subarray is the best one that lies entirely to its left, and the best third is the best one entirely to its right. Both can be precomputed:

    • leftMaxSum[i] is the best subarray sum inside nums[0..i];
    • rightMaxSum[i] is the best subarray sum inside nums[i..n-1].

    Then each middle range [i, j] is scored as leftMaxSum[i-1] + sum(nums[i..j]) + rightMaxSum[j+1]. Trying all middle ranges costs O(n²), because there are about n²/2 of them and the running sum makes each one constant work. Another lesson on this problem removes the inner loop.

    Step by step

    1. Store n, the length of nums.
    2. Create leftMaxSum with make([]int, n).
    3. Seed it: leftMaxSum[0] = nums[0], the only subarray of a one-element prefix.
    4. Track the best sum ending at the current index in maxSum, starting at nums[0].
    5. Loop from index 1 to n - 1.
    6. Update maxSum to nums[i] + max(maxSum, 0): extend the previous run if it is positive, otherwise start fresh at nums[i].
    7. Update leftMaxSum[i] to max(leftMaxSum[i-1], maxSum): the best in the prefix either ends at i or lies before it.
    8. Create rightMaxSum the same way and seed rightMaxSum[n-1] with nums[n-1].
    9. Reuse maxSum for the best sum starting at the current index, beginning at nums[n-1].
    10. Loop downward from n - 2 to 0. Set maxSum to nums[i] + max(maxSum, 0), then rightMaxSum[i] to max(rightMaxSum[i+1], maxSum).
    11. Reset maxSum to -(1 << 31) to hold the best answer. It must be lower than any possible total.
    12. Choose where the middle starts: i from 1 to n - 1, so the first subarray is not empty. Read sum1 as leftMaxSum[i-1].
    13. Choose where the middle ends: j from i up to but not including n - 1, so the third subarray is not empty. Keep sum2 as a running sum of nums[i..j], and read sum3 as rightMaxSum[j+1].
    14. Keep the larger of maxSum and sum1 + sum2 + sum3, then return maxSum.

    The solution in Go

    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)
	for i := 1; i < n; i++ {
		sum1 := leftMaxSum[i-1]
		sum2 := 0
		for j := i; j < n-1; j++ {
			sum2 += nums[j]
			sum3 := rightMaxSum[j+1]
			maxSum = max(maxSum, sum1+sum2+sum3)
		}
	}

	return maxSum
}

    Go details:

    • := declares once, = reassigns. maxSum is declared with := the first time. Later lines use plain = to reuse it for a different purpose. Writing := again in the same scope would be a compile error because there would be no new variable.
    • Built-in max. Go 1.21 and later include max and min for ordered types, so the code needs no helper.
    • A descending loop is written with the post statement i-- and the condition i >= 0. Since int is signed, the loop ends cleanly at -1.
    • The sentinel. -(1 << 31) is -2147483648. It is far below any total for ordinary inputs, but sums beyond that range would not be handled correctly.

    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]. Take the middle range at indices 3 to 5 ([7, -2, 9]). Then sum1 = leftMaxSum[2] = 5, sum2 = 14 and sum3 = rightMaxSum[6] = 9, for a total of 28. No other middle range gives more.

    Why the recurrence works

    The line maxSum = nums[i] + max(maxSum, 0) is the heart of the precomputation. A subarray that ends at i either is just nums[i] or continues a subarray that ended at i-1. Continuing helps only when that earlier sum is positive, so the code adds max(maxSum, 0). The prefix table then takes the larger of the previous prefix answer and this run, because the best subarray of nums[0..i] either ends at i or lies completely before it. The suffix table is the mirror image, scanning from the right.

    Complexity

    Time: O(n²). The two precomputing passes are O(n). The final nested loops visit each pair (i, j) with i <= j once, about n²/2 pairs, with constant work each.

    Space: O(n). The two arrays hold n values each.

    Edge cases and common mistakes

    • Exactly three numbers. Each subarray is one element, and the answer is their sum. The loops allow only i = 1 and j = 1.
    • All negative numbers. For [-1, -2, -3] the answer is -6, since all three must be used. Starting the final maxSum at 0 would give a wrong answer.
    • All positive numbers. For [1, 2, 3, 4, 5] the answer is 15: the three subarrays together can cover everything.
    • Overlapping subarrays. sum1 must come from leftMaxSum[i-1] and sum3 from rightMaxSum[j+1]. Using index i or j would let the outer subarrays share elements with the middle.
    • Empty outer subarrays. The bounds i >= 1 and j <= n-2 keep both outer subarrays non-empty.
    • Resetting the running sum. sum2 must be created per i, inside the outer loop.

    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