Don't memorize Kadane’s algorithm — watch the best streak emerge. Sweep the array once keeping a running sum. The moment that sum turns negative, throw it away and start fresh — a negative head start can only drag down whatever comes next. Track the best total you have seen, and that is the maximum-sum subarray, in a single O(n) pass.
maximum subarray · running sum · restart · O(n)
CURRENT SUM
The best subarray sum ending exactly at the current index.
RESTART
If current sum ≤ 0, drop it and begin again at this element.
BEST SUM
The largest current sum seen anywhere — the answer.
ONE PASS
Each element seen once, O(n) time, O(1) space.
kadane.sim — maximum-sum subarray
Ready
An array with negatives. Press Step to sweep left to right. The purple window is the current run; the green outline is the best run found so far.
0
Current sum
—
Best sum
A greedy decision, made local
The brute force tries every start and every end — O(n²) subarrays, or O(n³) if you re-add each one. Kadane collapses that into a single question asked at every index: what is the best subarray that ends right here? It is either this element alone, or this element added to the best subarray ending just before it — whichever is larger. If the running sum ever goes non-positive, "this element alone" wins and the window restarts. Keep the maximum of those answers and you are done.
01
Extend or restart
At each element, set cur = max(A[i], cur + A[i]). A negative running sum is dropped in favor of starting fresh.
02
Track the best
Set best = max(best, cur) every step. The best is the answer, wherever it occurred.
03
Why restart works
A negative prefix can only reduce any subarray it is glued to, so discarding it is never worse — the key insight that makes it correct.
04
All-negative case
Initialize best to −∞ and take the element itself on restart, so the answer is the largest single number.
Time
O(n)
Space
O(1)
Brute force
O(n²)
Type
DP
Kadane is the classic “aha” dynamic program: the subproblem is “best subarray ending at i”, and the recurrence reuses the answer for i−1. The same idea extends to the maximum-product subarray (track both max and min because a negative flips them) and to 2-D via a maximum-sum-rectangle reduction.
SOLVE IT YOURSELF
Solve it: maximum subarray
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement max_subarray(nums): return the largest sum of any contiguous subarray (at least one element). Kadane’s trick is one pass — carry the best sum ending at the current position and track the best seen overall. O(n) time, O(1) space.
HINTS — 4 IDEAS
Keep best_here = the largest sum of a subarray that ends at the current element.
At each element x: either extend the previous run or start fresh at x — best_here = max(x, best_here + x).
Keep a separate best = the largest best_here seen so far.
Start both at nums[0] and scan from index 1, so all-negative arrays return their largest single element.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · What does Kadane do when the running current sum drops to zero or below?
A non-positive prefix can only hurt what follows, so it is dropped and the current window restarts fresh.
2 · What is the time complexity of Kadane’s algorithm?
A single pass touching each element once with constant work — linear time, constant space.
3 · The subproblem Kadane solves at each index is:
That local answer, maximized over all indices, is the global maximum subarray — a clean dynamic program.
Questions
How do you also return the subarray, not just the sum?
Track the start index whenever you restart the window, and the end index whenever you update the best. When best improves, record the current start and the current index as the best range.
What about maximum product subarray?
Products behave differently because a negative times a negative is positive, so you track both the running maximum and minimum product at each step and swap them when you hit a negative number. Same one-pass shape, two variables.
Why is this considered dynamic programming?
Because the answer at index i is built directly from the answer at i−1 (extend it or restart), which is the essence of DP: optimal substructure plus reuse of a previously computed result.
One sweep, one running sum, the best streak wins.
Drop the negatives, keep the best. The maximum-subarray classic in O(n).