The site's sixth dynamic programming entry, and the first with a genuinely different shape from the other five. Longest Common Subsequence, Edit Distance, 0/1 Knapsack, and Weighted Interval Scheduling all fill a table whose cells depend on earlier rows or arbitrary earlier columns; Longest Increasing Subsequence's fast route replaces the table with a binary search instead. Kadane's Algorithm needs neither: solving the maximum subarray problem — given an array of numbers, positive and negative, find the contiguous run with the largest sum — only ever needs the single number computed one step ago. One left-to-right pass, one running value carried forward, one comparison per element.
Two presets: a mixed array with both signs (the classic textbook example), and an all-negative array that
exists specifically to break a common shortcut (see Pitfalls). Press Step
or Run to watch dp[i] — the best sum for a subarray ending exactly at
index i — fill in left to right, extending the previous run or starting fresh at each element. The
zero-init checkbox switches in a common buggy initialization (explained below) that silently
allows the empty subarray as a candidate answer.
Define dp[i] as the largest sum of any contiguous subarray that ends exactly at index
i (not the best subarray anywhere in the prefix — that distinction matters, see below). Every
element faces exactly one yes-or-no question: does the subarray ending at i-1 extend to include
i, or does a new subarray start fresh at i? Extending is worth
dp[i-1] + a[i]; starting fresh is worth a[i] alone. Extending only helps when
dp[i-1] is positive — adding a non-positive number can never make a running sum bigger, so the
recurrence keeps whichever option is larger: dp[i] = max(a[i], dp[i-1] + a[i]). The answer to the
whole problem is max(dp[0..n-1]), since the best subarray overall has to end somewhere,
and every possible ending point is covered. Because each dp[i] only ever needs
dp[i-1], the whole array of intermediate values collapses to one running variable — the table
shown above is really just a visualization of a single number changing over time, not a structure the
algorithm itself needs to keep around.
On the default mixed preset, this plays out as: dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]. The running
sum resets twice — at index 1 (1 beats extending -2 into -1) and again
at index 3 (4 beats extending -2 into 2) — and every index from 3
onward extends that second run, peaking at dp[6] = 6. The maximum over the whole array is
6, achieved by the subarray a[3..6] = [4, -1, 2, 1], confirmed against an independent
brute-force check of all 45 possible subarrays on this 9-element array — not just this one pass.
Tracks currentStart alongside the running sum purely for bookkeeping — recovering
which subarray achieves the maximum takes the same "remember where each candidate run began" trick
every other DP page on this site pairs with a bare table (compare Weighted Interval Scheduling's predecessor array):
function maxSubarray(arr) {
let currentSum = arr[0];
let currentStart = 0;
let best = arr[0];
let bestStart = 0;
let bestEnd = 0;
for (let i = 1; i < arr.length; i++) {
const extended = currentSum + arr[i];
if (extended >= arr[i]) {
currentSum = extended; // extend the running subarray
} else {
currentSum = arr[i]; // start fresh at i
currentStart = i;
}
if (currentSum > best) {
best = currentSum;
bestStart = currentStart;
bestEnd = i;
}
}
return { sum: best, start: bestStart, end: bestEnd };
}Initializing the running sum and the answer to zero silently allows the empty subarray, which
is wrong whenever every element is negative. It's tempting to write currentSum = 0,
best = 0 instead of seeding both from arr[0] — it looks harmless, and on any array
containing at least one non-negative number it happens to return the identical answer, since the true best
subarray sum is never below zero anyway. It stops being harmless the moment every element is negative. Switch
to the all-negative preset above (-3, -1, -4, -1, -5) and check the
zero-init box: the correct algorithm reports -1 (the single-element subarray
[-1] at index 1 — verified against an independent brute-force check of all 15 subarrays), while
the zero-init version reports 0 from the empty subarray, which was never a legal answer to begin
with — this page's own problem statement asks for a contiguous subarray, and the empty one isn't one.
Both numbers come from running the actual code above through the demo, not a hand-picked illustration.
The same all-negative run also shows a quieter tie that never gets reported. Watch the
table on the correct (non-zero-init) run: dp[3] reaches -1 again — exactly tying
the running best set back at dp[1] — but the demo's currentSum > best comparison
is strict, so index 1 keeps the win and index 3's tie is silently discarded. A version that used
>= instead would report index 3's [-1] alone as the answer instead — an equally
valid, equally sized, but different subarray. The same tie-break ambiguity Weighted Interval Scheduling's own Pitfalls
section raises about its backtracking: the optimal sum is never ambiguous, only which specific
optimal subarray gets reported when more than one achieves it.
"Largest sum" is easy to misread as "sum of every positive element," a different and much easier
problem. That version doesn't require the elements to be contiguous at all — it's really
asking for the best non-contiguous subsequence, which is solved by simply keeping every positive number and
throwing the rest away. On the default mixed preset, summing every positive element
(1 + 4 + 2 + 1 + 4) gives 12, computed live and shown in the result line once a run
finishes — nearly double this page's actual, contiguous-only answer of 6, and not a valid
answer to the maximum subarray problem at all, since no contiguous run of this array sums to
12 (confirmed by the same 45-subarray brute-force check above).
Time: O(n) — one comparison per element, a single pass, no nested loop and
no binary search. Space: O(1) beyond the input array itself — just the running
sum, the running best, and (if the actual subarray is wanted, not just its sum) two index variables. Every
other dynamic-programming page on this site needs at least O(n) space to hold a full table or
array for backtracking; Kadane's Algorithm is the first entry in the category that needs none of it, because
each cell only ever depends on the one immediately before it.
The same "extend or restart" recurrence shows up wherever a best-so-far value should reset itself the moment it turns unfavorable rather than dragging a bad start forward forever: the classic "buy low, sell high" single-transaction stock problem is exactly this algorithm run over day-to-day price differences instead of raw values, and the 2D generalization — largest-sum rectangle in a matrix — reduces to running this same 1D pass once per pair of matrix rows.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.