Run it
Kadane with the running values printed at each element, then the index-tracking version, then the zero-initialised variant getting an all-negative array wrong.
Kadane's algorithm
O(n) time, O(1) space, four lines.
The whole algorithm is that one decision: at each element, either extend the subarray ending at the previous element, or start a new one here. Extending is worth it only if the running sum so far is positive — if it is negative, it can only reduce whatever follows, so discard it.
Equivalently:
Both forms are the same rule. The max(x, current + x) version is the one usually written, because it reads as the decision it encodes.
Tracing it
[-2, 1, -3, 4, -1, 2, 1, -5, 4]:
| x | current | best | Decision |
|---|
| −2 | −2 | −2 | Start |
| 1 | 1 | 1 | Start fresh — −2+1 = −1 is worse than 1 |
| −3 | −2 | 1 | Extend (1−3 = −2 beats −3) |
| 4 | 4 | 4 | Start fresh |
| −1 | 3 | 4 | Extend |
| 2 | 5 | 5 | Extend |
| 1 | 6 | 6 | Extend |
| −5 | 1 | 6 | Extend |
| 4 | 5 | 6 | Extend |
The answer is 6. Note that current drops to 1 at the −5 and never recovers enough to beat 6 — which is why best is tracked separately rather than returned as the final current.
That separation is the most common bug: returning current gives the best subarray ending at the last element, not the best overall.
The one decision
At element i there are exactly two candidates for the best subarray ending there: the previous best-ending-here extended by values[i], or values[i] alone. Take the larger. Then the global answer is the largest of those per-element bests.
That is dynamic programming with the table collapsed to a single variable, because each step only needs the one before it. Saying that out loud is worth more than the code.
The edge case that catches people
Initialise best and current to values[0], not to 0. Starting at zero means an all-negative array returns 0 — a sum from the empty subarray, which is usually not allowed.
Ask whether the empty subarray counts. If it does, zero is the right floor; if not, the first element is. Getting this wrong is the most common failure on this question, and asking about it is a positive signal.
Returning the indices
The usual follow-up. Track where the current run started, and when you beat the best, record that start and the current index. Two extra variables and no change to the complexity — but you must update start at the moment you restart, not when you improve.
The other follow-up is divide and conquer: split, solve both halves, and handle the crossing case separately. O(n log n), worse than Kadane, and worth knowing because it is the classic example of the crossing-subproblem pattern.
The all-negative case
The trap that catches most first attempts. With [-3, -1, -2], what is the answer?
If the subarray must be non-empty: −1, the least bad single element. The code above handles this correctly, because it initialises best to nums[0] rather than to 0.
If an empty subarray is allowed: 0. Then initialise best = 0.
Initialising best = 0 when the subarray must be non-empty is wrong, and it only shows up on all-negative input — which is exactly why interviewers include that test case.
Ask which convention applies. It is a legitimate clarifying question and demonstrates that you spotted the ambiguity.
Returning the subarray, not just the sum
Frequently the follow-up. Track where the current run started:
The addition is one variable and one branch. The start moves whenever a new run begins, and best_start is captured only when a new best is found — keeping those separate is the part that needs care.
The variants
| Problem | Change |
|---|
| Maximum product subarray | Track both max and min — a negative times a negative flips |
| Circular maximum subarray | The answer is either normal Kadane, or total minus the minimum subarray |
| At most k elements | Sliding window with a deque, or prefix sums |
| Maximum sum with one deletion allowed | Two DP states: with and without a deletion used |
| 2D maximum submatrix | Fix a column pair, compress rows, run Kadane — O(n²m) |
| Longest subarray with sum ≤ k | Prefix sums plus binary search or a monotonic structure |
Maximum product is the most common escalation, and the reason it is harder is instructive: with sums, a negative running total is always worth discarding. With products, a very negative running product becomes the maximum as soon as another negative appears — so both the maximum and minimum must be tracked.
Circular is elegant: either the best subarray does not wrap, in which case plain Kadane finds it, or it does wrap, in which case its complement is a non-wrapping minimum subarray. Compute both and take the larger, with a special case when every element is negative.
Why it is a dynamic programming problem
Kadane's algorithm is dynamic programming with the table collapsed to a single variable.
The DP formulation: let dp[i] be the maximum sum of a subarray ending at index i. Then
dp[i] = max(nums[i], dp[i−1] + nums[i])
and the answer is max(dp).
Because dp[i] depends only on dp[i-1], the array is unnecessary — one variable suffices, and space drops from O(n) to O(1).
That reduction is worth recognising as a general technique: when a DP state depends only on a bounded window of previous states, the table collapses to a few variables. The same trick turns Fibonacci from O(n) space to O(1), and applies to a large family of one-dimensional DP problems.
Framing Kadane as DP is also the better answer in an interview, because it shows the structure rather than a memorised trick.
Questions people ask
What if all numbers are negative? Return the largest single element, unless an empty subarray is allowed. Ask which convention applies.
Why track best separately from current? current is the best subarray ending at the current position; the overall answer may have ended earlier.
Is this greedy or dynamic programming? DP with an O(1) space optimisation. It is greedy-looking because the state is one variable.
How do I return the indices? Track where the current run started, and capture the bounds when a new best is found.
Does it work with zeros? Yes — a zero neither helps nor hurts, and extending across it is handled by the same comparison.
What about the maximum product version? Track the running maximum and minimum, because multiplying by a negative swaps them.
Recap in one screen
- At each element, either extend the previous subarray or start fresh — extend only if the running sum is positive.
- O(n) time, O(1) space, and track
best separately from current. - Initialise
best to the first element, not to 0, or all-negative input returns the wrong answer. - It is dynamic programming with the table collapsed to one variable, which is the better way to describe it.
- The standard escalations are maximum product, circular arrays and returning the subarray itself.