Maximum subarray (Kadane's algorithm)

Big idea

To find the largest sum of any contiguous subarray, walk once and keep the best sum of a subarray ending right here. At each item there are only two choices: extend the previous run, or start fresh at this item — whichever is bigger. That's Kadane's algorithm: O(n) time, O(1) space.

The brute force first

There are n(n+1)/2 subarrays. Summing each from scratch is O(n³); keeping a running sum per start index is O(n²). For n = 10⁵ that's still 5 × 10⁹ steps. We need one pass.

The key observation

Let cur be the best sum of a subarray that ends at index i. That subarray either:

• is just nums[i] on its own, or
• is the best subarray ending at i − 1, plus nums[i].

So cur = max(nums[i], cur + nums[i]). Put another way: if the run so far is negative, it can only hurt — drop it. The answer is the largest cur seen anywhere.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)     # extend or restart
        best = max(best, cur)
    return best

Trace it

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The answer is 6, from [4, −1, 2, 1]. Notice that the −1 is kept: dropping it would split a run whose total is still positive.

Watch it

Details that bite

• All negative numbers. Starting best at 0 would wrongly return 0 for [-3, -1, -2]. Start from nums[0] so the answer is −1.
• Returning the subarray itself. Record a start index when you restart, and save (start, i) whenever best improves.
• It's DP in disguise. cur is a one-variable dynamic programming table: state "best sum ending at i", transition "extend or restart".

Variations

• Maximum product subarray: a negative times a negative is positive, so track both the largest and smallest product ending at i, and swap them when x is negative.
• Circular array: the best wrap-around subarray is the total minus the minimum subarray. Answer = max(normal Kadane, total − min subarray) — unless every number is negative, in which case use normal Kadane.
• Best time to buy and sell a stock: Kadane on the day-to-day price differences.

Practice

• Maximum Subarray
• Maximum Product Subarray
• Maximum Sum Circular Subarray

Quick check