Kadane's Algorithm — Sweeping for the Maximum Subarray

bestEndingHere = max(a[i], bestEndingHere + a[i]); bestSoFar tracks the global maximum. Watch the recurrence extend or restart at each index.

step 0

Running state at index 0

bestEndingHere-
bestSoFar-
Press Step to begin the sweep.

Current vs best window

current run: —
best window so far: —
current run (ends at pointer) best window so far pointer i
We sweep left to right. At each index, the best subarray ending here is either a[i] alone (restart) or the previous run extended by a[i].
Self-contained visualization. The classic (non-empty) contract: both variables start at a[0], so an all-negative array correctly yields the least-negative element — never a phantom 0. See junior.md and professional.md for the proof that a negative running prefix is never worth carrying forward.