Start learning free

LESSON 209 OF 338 · PARTIAL SUMS #1

Maximum Sum Subarray in Go: O(n) with Prefix Sums

Practice O(n) Read the full explanation

( Prefix Sums Approach )


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    GO · PARTIAL SUMS #1

    Maximum Sum Subarray in Go, explained

    Problem overview

    The function maxSumSubarray receives a slice of integers, nums, that may include negative values, and returns the largest sum of any non-empty contiguous subarray.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from [6, -2, -3, 1, 5]. This version of the lesson uses prefix sums. It runs in O(n) time and may use up to O(n) extra space, although the solution below turns out to need only a few variables.

    Approach: a subarray sum is a difference of prefix sums

    Let the partial sum at position i be the sum of nums[0] through nums[i]. The subarray from l to i then has sum partialSum(i) - partialSum(l - 1), where the partial sum before the first element is 0.

    Fix the end position i. To make the subarray sum as large as possible, subtract the smallest prefix sum that lies before the subarray. That prefix can be the empty prefix, worth 0, so the minimum includes 0. So the best sum of a subarray ending at i is the current partial sum minus the smallest partial sum seen earlier (including the empty prefix). The answer is the largest of those values over all end positions.

    The earlier prefix sums are never needed individually, only their minimum, so one variable minSum replaces the whole prefix array.

    On the example, the partial sums are -2, -7, -1, -3, -6, -5, 0, -6. The smallest earlier prefix before each position is 0, -2, -7, -7, -7, -7, -7, -7. The differences are -2, -5, 6, 4, 1, 2, 7, 1. The largest is 7, at the position where the partial sum is 0 and the minimum is -7. The subarray between them is exactly [6, -2, -3, 1, 5].

    Step by step

    1. Create partialSum and minSum as 0. partialSum is the sum of everything visited so far, and minSum is the smallest partial sum seen so far. Both start at 0, the sum of the empty prefix.
    2. Create result from nums[0]. Not 0: when all values are negative, the answer is negative, and 0 would be a sum of no elements. nums[0] is a real subarray sum.
    3. Iterate over the values with for _, val := range nums.
    4. Add the value to partialSum.
    5. Update result. The best subarray ending here has sum partialSum - minSum, so take the larger of that and the current result.
    6. Update minSum. After using the minimum, fold in the current partial sum for later positions: minSum becomes the smaller of itself and partialSum.
    7. Return result.

    The order of steps 5 and 6 matters. If minSum were updated first, it could include the current partial sum, and the subarray would then be empty, with a difference of 0.

    The solution in Go

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

    Go details:

    • partialSum, minSum := 0, 0 declares two variables at once. Both are int, because untyped constants default to that type.
    • max and min are built-in functions since Go 1.21 and need no import.
    • The blank identifier in for _, val := range nums discards the index. An unused variable in Go is a compile error, so it can't just be left in.

    Complexity

    Time: O(n). One pass with constant work per element.

    Space: O(1). The statement allows O(n), which is what a stored prefix array would need, but tracking only the minimum prefix makes it constant. This solution and Kadane's algorithm compute the same thing in different words: partialSum - minSum is the best sum of a subarray ending at the current element.

    Edge cases and common mistakes

    • All elements negative. For [-3, -1, -2] the answer is -1. The partial sums are -3, -4, -6. Because minSum is updated after result, the differences are -3, -1 and -2, and the largest is -1.
    • Including the empty prefix. Starting minSum at 0 is what allows a subarray to begin at index 0. Starting it at nums[0] would miss subarrays that start at the front.
    • One element. [5] returns 5.
    • Updating in the wrong order. Updating minSum before result makes the difference 0 whenever the current prefix is the new minimum, which gives a wrong answer on all-negative input (0 instead of -1).
    • Empty slice. The solution reads nums[0], so an empty slice panics with an index-out-of-range error.

    Try in the editor above: the example should give 7, [-3, -1, -2] should give -1 and [5] should give 5.

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