Maximum Subarray

Maximum Subarray is the classic introduction to Kadane's algorithm — a tiny one-pass loop that finds the contiguous slice of an array with the largest sum. It looks almost too simple to be correct, and that is exactly why interviewers love it.

The slow way first

The brute force tries every possible subarray: pick a start, pick an end, add up everything between them, and keep the biggest total. There are about n²/2 subarrays, and summing each one takes time too — that lands at O(n²) or worse. For a long array it is far too slow.

The key question: as I walk left to right, do I even need to look back? It turns out the only thing I must remember is the best sum of a subarray that ends right where I am standing.

The idea: extend or restart

Walk the array once, carrying two numbers:

• cur — the largest sum of a subarray that ends at the current element.
• best — the largest sum we have seen anywhere so far.

At each new number, ask one question: is it better to extend the running subarray, or restart a fresh one here? That is just cur = max(num, cur + num). If cur + num is smaller than num alone, the old cur was dead weight (it was negative), so we throw it away and begin again at num. After updating cur, update best = max(best, cur).

The insight: a subarray that ends here is either just this number or the best subarray ending one step back, plus this number. We never need older history — only cur.

Walk through it

Step through the animation. The pointer num scans left to right. Watch cur swing: it restarts whenever the running sum has gone negative (at 1, then at 4), and extends otherwise. best only ever climbs. It hits 6 at the value 1 (the window [4, -1, 2, 1]) and never gets beaten — the later -5 drags cur down, but best remembers the high point.

Pseudocode

cur  = nums[0]            # best sum of a subarray ending here
best = nums[0]            # best sum seen anywhere
for num in the rest of nums:
    cur  = max(num, cur + num)   # extend the run, or restart at num
    best = max(best, cur)        # remember the best we have seen
return best

The Python solution

def max_subarray(nums):
    cur = nums[0]
    best = nums[0]
    for num in nums[1:]:
        cur = max(num, cur + num)
        best = max(best, cur)
    return best

• We seed both cur and best with nums[0] so the array can be a single (possibly negative) number.
• The loop starts at the second element (nums[1:]), since the first is already accounted for.
• Line 5 is the heart of Kadane: max(num, cur + num) decides extend vs. restart in O(1).
• Line 6 keeps best as the running maximum — cur may dip later, but best never forgets a peak.
• We return best, the largest contiguous sum.

Complexity

Kadane is O(n) time and O(1) space — we only ever keep two numbers, cur and best. That is the whole appeal: a linear scan with constant memory beats the quadratic brute force handily.

When this pattern shows up

Practice