A trading desk has ninety days of daily P&L. Product wants the best consecutive stretch — the run you would have wanted to stay in. The intern writes two nested loops: for every start i, for every end j, add a[i] through a[j]. That is every slice. Re-summing each pair is O(n³). Keeping a running total from i is still O(n²). Ninety days compiles. A year of minute bars does not.
The same job shows up as request-latency deltas: per-minute error-budget change, find the worst consecutive burn. Still every i..j. Still a quadratic bill for a question that only needs the hottest contiguous sum.
Kadane keeps the best sum ending at the current index, and the best seen so far — one pass. You do not enumerate slices. You decide, at each i, whether to extend the run that already ends at i - 1 or to start a new run at i.
This post is that loop. Families, greedy-vs-DP vocabulary, and the catalog live on the Algorithms Roadmap. You may call this linear DP if you want a name; you do not need a table. Two scalars are the table. The layout is already an array — index i is free, a full scan is the cheap job (Arrays). Kadane is the procedure you run on that scan.
The nested loops that try every slice
Nobody writes the cubic version because they love nested sums. They write it because the spec says “contiguous” and the obvious model is “every pair of endpoints.”
static int maxSubarrayCubic(int[] a) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += a[k];
}
best = Math.max(best, sum);
}
}
return best;
}Drop the inner re-sum and you still pay a pair of loops:
static int maxSubarrayQuadratic(int[] a) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
int sum = 0;
for (int j = i; j < a.length; j++) {
sum += a[j];
best = Math.max(best, sum);
}
}
return best;
}Prefix sums make each i..j a subtraction after one precompute. That is a different post in the catalog. It still leaves you with every pair to consider, so the max-slice job stays quadratic unless you stop asking “what is the sum of this pair?” and start asking “what is the best run that ends here?”
Every i..j is the wrong primitive once n is a scan, not a spreadsheet. Kadane’s move is to throw the pairs away.
The invariant: best ending here
At index i, any contiguous subarray that ends at i is either:
- the singleton
[a[i]], or - some subarray that ended at
i - 1, plusa[i].
You do not need every subarray that ended at i - 1. You need the best one. Call that bestEndingHere. Then:
best ending here = a[i] or bestEndingHere + a[i] — whichever is larger.
bestEndingHere = max(a[i], bestEndingHere + a[i])
bestSoFar = max(bestSoFar, bestEndingHere)That is the whole recurrence. bestEndingHere is the answer to a one-index question. bestSoFar is the global max of those answers. After the last index, bestSoFar is the maximum contiguous sum.
Why the singleton can win: if the best run ending at i - 1 is already negative, adding it makes a[i] worse. Starting fresh at i is then the only legal move that still ends here. You are not “skipping” an element in the middle of a slice — you are refusing to drag a losing prefix into the new end.
Note: This is optimal substructure with a one-cell memory. It is DP in the sense the roadmap uses the word. It is not a reason to allocate dp[n]. The previous cell is an int.
A walk: mixed signs, then all-negative
Classic mixed array. The answer is the slice [4, -1, 2, 1] with sum 6.
a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i a[i] a[i] vs prev+a[i] bestEndingHere bestSoFar
0 -2 start -2 -2
1 1 1 > -2+1 1 1
2 -3 -2 > -3 -2 1
3 4 4 > -2+4 4 4
4 -1 3 > -1 3 4
5 2 5 > 2 5 5
6 1 6 > 1 6 6
7 -5 1 > -5 1 6
8 4 5 > 4 5 6
bestSoFar = 6At i = 1 the previous ending sum is -2. Extending it yields -1; starting at 1 yields 1. Start. At i = 3 the previous ending is -2; extending yields 2, but 4 alone is better, so the run that will become the answer starts here. The later -1 is kept because 4 + -1 still beats starting over. That is the contiguous contract: you may drop a prefix, never a hole in the middle.
Now all-negative. There is no positive run to extend into. If the problem requires a non-empty subarray, the answer is the largest (least negative) element.
a = [-3, -1, -2]
i a[i] a[i] vs prev+a[i] bestEndingHere bestSoFar
0 -3 start -3 -3
1 -1 -1 > -3-1 -1 -1
2 -2 -1 > -1-2 -1 -1
bestSoFar = -1 (the singleton -1)At every step the singleton wins because every extension is more negative. bestSoFar never resets to 0. That is correct for “must pick at least one.” It is the case the reset-to-zero rewrite gets wrong.
Empty array, or must pick at least one?
Two different specs share the name “maximum subarray.” Mixing them is the production bug.
Must pick at least one. The subarray is non-empty. An empty input has no answer — throw. An all-negative input returns the largest element, which may be negative. The walk above is this spec. Interview statements that say “contiguous subarray” without mentioning empty almost always mean this.
Allow empty, sum 0. The empty slice is legal and sums to 0. Then any all-negative array loses to empty, and the answer is 0. A common rewrite of the recurrence is:
bestEndingHere = max(0, bestEndingHere + a[i]) // empty is allowedThat clamp is not a speed hack. It changes the problem. It is also what you get if you initialize bestSoFar = 0 and then only update when a running sum goes positive.
Name the spec at the method boundary. An empty int[] (length == 0) is not “all zeros.” There is no a[0]. If the caller can pass it, decide before the loop.
Note: Do not initialize bestSoFar to 0 and then claim you handle all-negative. Zero is the empty-slice answer smuggled into the non-empty spec. Initialize from a[0] when the array must contribute at least one element. Returning 0 without documenting “empty allowed” will pass a green test suite that never sent negatives, then fail the first all-red P&L week.
Java: one loop, two ints
There is no Arrays.maxSubarray. The JDK map on the roadmap lists sorts, binary search, shuffle, and queues. This job is a loop you write.
Non-empty spec, matching the walks:
static int maxSubarray(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException("need at least one element");
}
int bestEndingHere = a[0];
int bestSoFar = a[0];
for (int i = 1; i < a.length; i++) {
bestEndingHere = Math.max(a[i], bestEndingHere + a[i]);
bestSoFar = Math.max(bestSoFar, bestEndingHere);
}
return bestSoFar;
}Allow-empty spec, for contrast. The clamp is the spec, not an optimization:
static int maxSubarrayAllowEmpty(int[] a) {
int bestEndingHere = 0;
int bestSoFar = 0;
for (int value : a) {
bestEndingHere = Math.max(0, bestEndingHere + value);
bestSoFar = Math.max(bestSoFar, bestEndingHere);
}
return bestSoFar;
}Note: Sums of int P&L can overflow. If the domain is money or counters that do not fit in 32 bits, use long for both running values. Overflow is Java’s wrap, not Kadane’s failure mode.
You can run the same two scalars on a stream. That is the “online” Kadane the roadmap names: you never need the prefix again, only the best ending here and the best so far.
Recovering the slice when you need indices
Kadane’s scalars answer “how much.” Dashboards and tickets often need “which days.” Track the candidate start of the current ending run, and commit start/end when bestSoFar improves.
static int[] maxSubarrayRange(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException("need at least one element");
}
int bestEndingHere = a[0];
int bestSoFar = a[0];
int start = 0;
int bestStart = 0;
int bestEnd = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] > bestEndingHere + a[i]) {
bestEndingHere = a[i];
start = i;
} else {
bestEndingHere += a[i];
}
if (bestEndingHere > bestSoFar) {
bestSoFar = bestEndingHere;
bestStart = start;
bestEnd = i;
}
}
return new int[] {bestSoFar, bestStart, bestEnd}; // inclusive indices
}On the mixed walk, bestStart becomes 3 when the run restarts at 4, and bestEnd becomes 6 when bestSoFar hits 6. Strict > keeps the earliest slice on ties. If the spec wants the longest among equals, change the commit condition; do not pretend the scalar-only loop remembered a length it never stored.
Note: Returning only bestSoFar and then scanning again for a subarray that sums to it can disagree on ties and re-pays a search you already did. If you need indices, keep them in the same pass.
Complexity
| What | Cost | Why |
|---|---|---|
| Time | O(n) | One visit per index; max is O(1) |
| Extra space | O(1) | Two running ints (plus three index ints if you recover the slice) |
| Nested every-slice | O(n²) or O(n³) | Every pair, optionally re-summed |
| Output | O(1) or O(k) | The sum, or a copy of the slice of length k if you materialize it |
The input array is O(n) whoever owns it. Kadane does not allocate a second n-sized table. One pass, constant extra memory, no JDK helper. A correct cubic nested sum is still the wrong default on minute bars.
When not to use Kadane
Skip this loop when the job is not “maximum contiguous 1D sum.”
- You need the actual subarray, not only the sum. The two-int loop does not remember bounds. Use the index-tracking variant above. Do not re-scan for a matching sum afterward and call it Kadane.
- The picks need not be contiguous. If you may skip elements, the answer on mixed signs is “take every positive” (or the largest element if all are negative). That is a filter, not Kadane. Longest common subsequence and knapsack live in the DP family on the roadmap; they are different jobs.
- The array wraps. Maximum circular subarray (the slice may run off the end and continue at
0) is not the linear invariant. Standard Kadane misses the wrap. Treat circular as a different bill — often “total minus minimum subarray,” with the all-negative case as its own trap — not a flag you pass to the loop above. - 2D maximum subrectangle. Fix a pair of rows (or columns), compress the other axis into a 1D temp, run Kadane on the temp, repeat. That is
O(rows² · cols)(or the symmetric). People still say “2D Kadane.” The 1D pass is a subroutine, not the whole invoice. Do not quoteO(n)for a matrix. - You needed a range-sum API, not a max. If the hot path is “sum of
i..jmany times,” precompute prefix sums. Kadane answers one global max, not arbitrary ranges. - The constraint is a window length. “Best sum among subarrays of length
k” is a sliding window (or a prefix difference of widthk), not an unbounded restart-or-extend choice.
Contiguous, 1D, one global max — that is the job. Anything else is a different procedure that may call this loop.
Cheat sheet
Job: maximum contiguous sum (1D)
Invariant: bestEndingHere = max(a[i], bestEndingHere + a[i])
Global: bestSoFar = max(bestSoFar, bestEndingHere)
Empty: throw if non-empty required; 0 if empty is a legal slice
All-neg: max element if non-empty; 0 if empty allowed
Indices: track candidate start; commit on bestSoFar improve
Time/space: O(n) / O(1) extra
JDK: none — write the loop
Not this: non-contiguous, circular wrap, 2D subrectangle, fixed window kDo:
- Name the spec first: non-empty vs empty-allowed.
- Initialize
bestEndingHereandbestSoFarfroma[0]when at least one element is required. - Recover
[start, end]in the same pass if the caller needs the days, not only the dollars. - Use
longwhen the sum may not fit inint.
Don’t:
- Try every
i..joncenis a scan. - Clamp to
0inside the loop and still claim you handle all-negative non-empty input. - Quote 1D Kadane’s
O(n)for a 2D subrectangle or a wrap-around slice. - Look for
Arrays.maxSubarray. There is not one.
Wrap-up
Kadane replaces “every contiguous slice” with one decision per index: extend the best run that already ends here, or start over at i. Two integers keep the recurrence; the global max is a running max of those endings. Empty input and all-negative input are spec, not edge-case folklore — pick non-empty or allow-empty before you write the initializer.
The layout was already an array. The procedure is this pass. When you need the bounds, keep them beside the sums. When the job is non-contiguous, circular, or 2D, this loop is the wrong named procedure — start from the Algorithms Roadmap and pick the job again.