Given a row of numbers, some positive, some negative, find the contiguous stretch with the largest sum. The brute force checks every stretch; Kadane’s algorithm does it in a single pass by asking one question at each step: is it better to extend the current run, or start fresh here? It runs in real I-13 over the new array.
THE TECHNIQUE extend, or restart — keep the best seen
Track the best sum ending here: it is either this element alone, or this element plus the best-ending-at-the-previous. Keep the largest such value ever seen. The green cells are the current best window. live demo
HISTORY & CREDIT from a 2-D image problem to a one-liner
Told as “Kadane invented it” — the fuller story is a lone genius versus a chain of people and a harder original problem. cited
the origin · Ulf Grenander posed the two-dimensional maximum-sum submatrix problem (image pattern recognition); the brute force was O(n⁶). the reduction · Grenander himself simplified the problem to 1-D to see its structure; Michael Shamos, hearing the 1-D version, found an O(n log n) divide-and-conquer overnight. 1977 · Jay Kadane, shown the 1-D problem at a Carnegie Mellon seminar, gave the O(n) single-pass algorithm in about a minute. 1984 · Jon Bentley features it in Programming Pearls, making it famous as a lesson in algorithm design.
The elegant one-liner is the last link in a chain that started two dimensions up. a chain
RECOMMEND FOR I-13 a no-wall over the array
Kadane needs only indexed reads and two running scalars — the array carries the input, the state is numbers. It runs:
def kad(I a, I i, I n, I cur, I best) {
if i >= n { -> best }
I x <- a[i]
I nc <- x
if cur + x > x { nc <- cur + x } // extend, or restart at x
I nb <- best
if nc > best { nb <- nc }
-> kad(a, i + 1, n, nc, nb)
}
$ i13 run kadane.i13 # over [-2,1,-3,4,-1,2,1,-5,4]
best = 6 # the run [4,-1,2,1]
Recommend:nothing new — a clean no-wall, and a good measure of how far the language has come: an algorithm that was pure “aggregate wall” a day ago now runs unchanged from its textbook form. The array made input a first-class thing; the rest was always in reach. Note: the running fold (extend-or-restart) is I-13’s native shape — bounded recursion carrying an accumulator. The array just gave it something to fold over.