Kadane's Algorithm

Kadane's algorithm finds the largest sum of any contiguous slice of an array in a single left-to-right pass. The trick is a running-sum dynamic program: at every position you only need one number — the best sum that ends right here — and you carry it forward, restarting whenever the past is dragging you down.

The classic problem: Maximum Subarray. Among all contiguous slices, return the one with the greatest sum. A brute-force check of every slice is O(n²); Kadane does it in O(n).

Intuition

Walk along the array carrying a running total. At each new element x you face one decision: is the sum you have been building still worth keeping, or should you throw it away and start fresh from x?

If cur + x is bigger than x by itself, the past is helping — extend the window. If x alone is bigger, the past total was negative baggage — restart the window at x. That single comparison, max(x, cur + x), is the whole algorithm. Every time cur reaches a new high, you stamp it into best.

Walk through it

Step through the animation on the right. The i pointer scans nums left to right. The cur and best labels update at the top; the highlighted cells show the window that currently sums to cur (the locked best window stays marked).

Start with cur = best = -2. At index 1 (value 1), cur + x = -1 but x = 1 is bigger, so the window restarts at 1 and best jumps to 1. Index 2 (value -3) drags cur down to -2. At index 3 (value 4), -2 + 4 = 2 loses to 4 alone, so the window restarts again at 4, and best becomes 4. From there the window only grows: -1, then 2, then 1 push cur up to 3, 5, 6 — each a new best. Index 7 (value -5) drops cur to 1 but best stays 6. Index 8 (value 4) lifts cur to 5, still under 6. Final answer: best = 6, the slice [4, -1, 2, 1].

The code, line by line

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

• Lines 2–3 seed both values with the first element, so the answer is always a non-empty subarray.
• The loop starts at the second element (nums[1:]) because the first already initialized cur and best.
• Line 5 is the heart of it: max(x, cur + x) either extends the running window or restarts it at x when the carried sum has gone negative.
• Line 6 records the running maximum — cur is only the best ending here, so we keep a separate best for the answer.
• We never store the slice itself, only its sum; tracking the start and end indices is a small extra bookkeeping step if the actual subarray is needed.

Complexity

Each element is visited exactly once and does a single max comparison, so the total work is linear. Nothing about the array is stored beyond two scalars, making it the textbook example of an O(1)-space running-sum DP.

When to use / pitfalls

Practice