Kadane's maximum subarray
Scan once, greedily restarting or extending a running sum to find the best contiguous block. · 9 min read
The problem
Given an array of numbers (possibly negative), find the contiguous subarray with the largest sum. Checking every subarray is O(n²); Kadane's algorithm does it in a single O(n) pass.
The greedy choice
Scan left to right keeping cur = the best sum of a subarray ending at the current element. At each new element x you make one local choice: extend the previous block (cur + x) or restart a fresh block at x. Take whichever is larger — that's the greedy step. Track the best cur ever seen.
cur = max(x, cur + x) # restart vs extend
best = max(best, cur)It's a greedy/DP hybrid: cur is a one-state DP recurrence, and the "restart when the running sum would only hurt" rule is the greedy insight — once cur goes negative it can never help a future element, so drop it.
Interactive visualization: Kadane: restart vs extend, tracking the best window — step through it frame by frame on this page.
cur tracks the best sum ending here— Either extend or restart.a negative cur can only lower a future sum— So restart drops it.one pass, O(1) state— best updates as we go.
Result: O(n) time, O(1) space
Variations
The same scan adapts: track the indices for the actual subarray, or keep both a running max and min product to handle maximum product subarray (a negative times a small negative can become large).
Practice: Maximum Subarray (Medium) — Largest sum of any contiguous subarray (Kadane's algorithm).
Practice: Maximum Product Subarray (Hard) — Largest product of a contiguous subarray — track max AND min.