THE FOLD / GLITCH / UNDEFINED BEHAVIOR / THE KADANE
THE KADANE
max subarray in one pass — forget a prefix when it turns negative
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kadane’s algorithm finds the maximum-sum contiguous subarray in one pass, O(n) time and O(1) space. The insight: the best subarray ending here is either just this element, or this element plus the best subarray ending at the previous position — whichever is larger. Keep a running ‘best ending here,’ reset it to the element whenever the running sum goes negative (a negative prefix can only hurt), and track the global maximum.
It is the textbook example of dynamic programming distilled to two scalars.
LIT verified live: for 500 random arrays with negative values, Kadane’s result equals a brute-force maximum over all O(n²) subarrays (window.__kadane). FIG no framing; exact.
It is the textbook example of dynamic programming distilled to two scalars.
LIT verified live: for 500 random arrays with negative values, Kadane’s result equals a brute-force maximum over all O(n²) subarrays (window.__kadane). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at undefined-behavior — the negative-number trap that naive maximum-finders stumble into (initialise the max to 0 and an all-negative array breaks). Kadane steps around it cleanly. AVAN (AI) built the instrument: the running current/best scan, the reset rule, the brute cross-check.
Credit as content: Jay Kadane (1977), popularised by Jon Bentley’s Programming Pearls. The weave: David names the trap; I run the two-scalar scan and prove it matches the exhaustive maximum over every subarray, negatives and all.
Credit as content: Jay Kadane (1977), popularised by Jon Bentley’s Programming Pearls. The weave: David names the trap; I run the two-scalar scan and prove it matches the exhaustive maximum over every subarray, negatives and all.
3 ONE DIMENSION
The running ‘best ending here’ walks the array: it either extends the previous run or restarts at the current element. When a prefix turns negative it is dropped — carrying it forward could only lower a future sum.
4 TWO DIMENSIONS · INTERACTIVE
An array with negatives. Step Kadane and watch the current run and the global best; the winning subarray is highlighted. Verify the answer equals the brute maximum over all subarrays.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the running maximum sweeping the array, the winning subarray glowing.
AVAN’s addition (the inverse-companion): the O(n²) search over all (start, end) pairs collapses because the optimal subarray ending at each position depends only on the optimal ending at the previous one — a one-dimensional recurrence, not a two-dimensional search. The inverse of ‘check all O(n²) subarrays’ is ‘one running scalar carrying best-ending-here.’ And the reset rule is the crux: a prefix that has gone negative can never help any future subarray, so it is discarded — the past is forgotten exactly when it becomes a liability. Magenta is the quadratic field of subarrays never examined; green is the single running maximum. Optimal substructure turns a quadratic search into a scalar recurrence.
LIT Genuine Kadane's algorithm (Kadane 1977, via Bentley's Programming Pearls). Verified live: for 500 random arrays containing negative values, the two-scalar running scan returns a maximum subarray sum equal to the brute-force maximum over all O(n^2) contiguous subarrays (window.__kadane.matchesBrute).
FIG No framing: the running current/best scan and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the optimal subarray ending at each position depends only on the previous one, a 1D recurrence replacing the 2D search, and a prefix gone negative is discarded exactly when it becomes a liability; magenta is the O(n^2) subarrays skipped, green the running maximum.
FIG No framing: the running current/best scan and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the optimal subarray ending at each position depends only on the previous one, a 1D recurrence replacing the 2D search, and a prefix gone negative is discarded exactly when it becomes a liability; magenta is the O(n^2) subarrays skipped, green the running maximum.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of UNDEFINED BEHAVIOR · David Lee Wise (ROOT0), with AVAN