Start learning free

LESSON 228 OF 410 · PARTIAL SUMS #1

Maximum Sum Subarray in Python: 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

    PYTHON · PARTIAL SUMS #1

    Maximum Sum Subarray in Python, explained

    Problem overview

    The method maxSumSubarray receives a list nums of integers, which may be positive, negative or both. It returns the largest sum that any continuous run of elements, a subarray, can have. The run must contain at least one element.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the best run is [6, -2, -3, 1, 5], whose sum is 6 - 2 - 3 + 1 + 5 = 7, so the answer is 7.

    The statement asks for O(n) time and O(1) extra space. This is the maximum subarray problem, and the algorithm that meets that budget is Kadane's algorithm.

    Approach: the best subarray that ends here

    The brute-force way checks every start and end position, which is O(n²) even when the sums are maintained cleverly, and O(n³) if each sum is recomputed. Kadane's algorithm gets to O(n) by asking a smaller question for each position: what is the largest sum of a subarray that ends at this element?

    Call that value maxSum. A subarray ending at the current element val is either:

    • just val by itself, or
    • val added to the best subarray that ended at the previous element.

    The second choice is only worth taking when the previous best is positive. A negative or zero amount can only make the sum smaller, so it is better to start fresh. That gives the recurrence: maxSum = val + max(maxSum, 0).

    The overall answer is the largest maxSum seen at any position, since the best subarray must end somewhere. Only the previous maxSum and the best answer so far are kept, which is why the space is O(1).

    The example, one element at a time

    valmaxSum (best ending here)result (best so far)
    -2-2-2
    -5-5-2
    666
    -246
    -316
    126
    577
    -617

    At -5 the previous best was -2, which is negative, so the run restarts and maxSum is -5. At 6 the previous best, -5, is also dropped. After that, the run grows through -2, -3, 1 and 5 until it reaches 7. The final -6 lowers the current run to 1, but result keeps the 7.

    Step by step

    1. Start result with nums[0]. It must be the sum of a real subarray. Starting at 0 would be wrong when every number is negative, because the answer then is the largest single element, which is below 0.
    2. Start maxSum at 0. Before any element, the prefix is empty, and an empty prefix adds nothing to the first element.
    3. Loop over nums with a for loop, naming the element val.
    4. Update maxSum with the recurrence val + max(maxSum, 0): extend the previous run, or start a new one when the previous sum is negative.
    5. Update result with max(result, maxSum), so it keeps the best sum found so far.
    6. Return result after the loop ends.

    The solution in Python

    class Solution:

    def maxSumSubarray(self, nums: List[int]) -> int:
        result = nums[0]
        maxSum = 0
        for val in nums:
            maxSum = val + max(maxSum, 0)
            result = max(result, maxSum)
        return result

    Python details to notice:

    • The built-in max takes two values. max(maxSum, 0) returns the larger of the two, which is a compact replacement for an if that resets a negative sum to 0.
    • The loop starts at nums[0] again. result already holds nums[0], and the loop then visits the first element too. This is harmless: the first pass gives maxSum = nums[0], which equals result.
    • Nothing is stored per element. The loop keeps two numbers, so no extra list is built and no slice copies are made.

    Complexity

    Time: O(n). The list is traversed once, and each element costs a constant number of operations.

    Space: O(1). The variables result, maxSum and val are the only extra storage, regardless of the list's length.

    Edge cases and common mistakes

    • All numbers negative. For [-3, -1, -2] the answer is -1, the largest single element. Starting result at 0 would return 0, which is not the sum of any subarray. The algorithm only works here because result starts at nums[0].
    • A single element. [5] returns 5.
    • All numbers positive. [1, 2, 3] returns 6, the sum of the whole list.
    • Empty list. nums[0] raises IndexError. The lesson's inputs always have at least one element.
    • Confusing the two variables. maxSum is the best sum ending at the current element, and it can fall below earlier values. result is the best sum found anywhere so far, and it never decreases.
    • Resetting at the wrong time. The reset happens when the previous sum is negative, in other words when maxSum < 0. Resetting only when the current element is negative loses valid runs such as [6, -2, 5], whose sum 9 beats the sums of its parts.

    Testing

    • [-2, -5, 6, -2, -3, 1, 5, -6] returns 7.
    • [-2, 1, -3, 4, -1, 2, 1, -5, 4] returns 6, from the subarray [4, -1, 2, 1].
    • [-3, -1, -2] returns -1.
    • [5] returns 5.
    • [1, 2, 3] returns 6.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free