Start learning free

LESSON 208 OF 338 · PARTIAL SUMS #1

Maximum Sum Subarray in Go: Kadane's Algorithm in O(n)

Practice O(n) Read the full explanation

( Kadane's Algorithm )


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 O(1) extra space.


STEP 1 OF 6
    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, which may contain negative values. It returns the largest sum of any non-empty contiguous block of elements, called a subarray.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6], the best block is [6, -2, -3, 1, 5], which sums to 7. The lesson asks for O(n) time and O(1) extra space, which rules out trying every subarray (O(n²) or worse) and also rules out building a prefix array.

    Approach: the best subarray that ends here

    Kadane's algorithm rests on one observation. Every subarray ends at some position, so the answer is the largest of the values "best sum of a subarray ending exactly at position i", taken over all i.

    That per-position value has a simple recurrence. A subarray ending at i either consists of nums[i] alone, or extends a subarray that ended at i - 1. Extending only helps when the previous best sum is positive. If it is negative or zero, carrying it along can only make things worse, so the new subarray starts fresh. With maxSum as the best sum ending at the previous element:

    maxSum = val + max(maxSum, 0)

    Only the previous value is needed, so a single variable replaces an array, and the space stays O(1).

    On the example, maxSum takes these values, one per element: -2, -5, 6, 4, 1, 2, 7, 1. At -5 the previous best was -2, which is not worth extending, so it restarts at -5. At 6 it restarts again. Then the run 6, 4, 1, 2, 7 builds up, and the final -6 drops it to 1. The largest value seen, 7, is the answer.

    Step by step

    1. Create result from nums[0]. It holds the best subarray sum found so far. Starting at 0 would be wrong, because 0 is the sum of an empty subarray, and a slice of only negative numbers has a negative answer. nums[0] is itself a subarray sum, so it is a safe starting point.
    2. Create maxSum as 0. It stands for the best sum ending at the previous element. Before the first element there is no subarray, and 0 means "nothing to extend".
    3. Iterate over the values with for _, val := range nums. The blank identifier discards the index, because the loop never uses it.
    4. Apply the recurrence with maxSum = val + max(maxSum, 0): extend the previous run if its sum is positive, otherwise begin again at val.
    5. Update result with the larger of itself and maxSum, since maxSum is now the best sum of a subarray ending at this element.
    6. Return result when the loop finishes.

    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
}

    Go details:

    • max and min are built-in functions since Go 1.21, so they need no import. They accept two or more values of the same ordered type.
    • for _, val := range nums gives the index first and the value second. Go refuses unused variables, so the unused index is dropped with _.
    • The loop also visits nums[0] again. That is harmless: with maxSum at 0, the first step sets maxSum to nums[0].
    • int is 64 bits on common 64-bit platforms, and overflow wraps silently instead of raising an error, though lesson-sized sums stay far from the limit.

    Complexity

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

    Space: O(1). Two integers, result and maxSum, and the loop variable.

    Edge cases and common mistakes

    • All elements negative. [-3, -1, -2] returns -1: the best non-empty subarray is the single largest element. Starting result at 0 would wrongly return 0.
    • One element. [5] returns 5.
    • Whole slice is best. When every element is non-negative, the best block is the entire slice.
    • Resetting to zero instead of to val. Writing maxSum = max(maxSum + val, 0) allows an empty subarray, which again fails on all-negative input. The restart has to begin at val.
    • Empty slice. The solution reads nums[0], so an empty slice panics with an index-out-of-range error. The lesson's inputs always have at least one element.
    • Returning maxSum instead of result. At the end of the example, maxSum is 1, not 7. It only describes subarrays ending at the last element.

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

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