Maximum subarray sum (Kadane)

At each element, one decision: extend the run you are on, or start again from here. Take whichever gives the larger sum, and track the best seen. One pass, two variables, O(n) time and O(1) space.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • The lighter band is the current run; the solid one is the best so far.
  • A run restarts whenever carrying the previous sum would hurt.
  • The best is only updated — never reduced.

Say this out loud

"Kadane. At each element I either extend the current run or start fresh from that element, whichever is bigger, and I keep the best I've seen. O(n) time, O(1) space - and I initialise from the first element, not zero, so all-negative input works."

Overview

The maximum-subarray problem asks for a non-empty contiguous range with the greatest sum. Kadane’s algorithm either extends the previous range or starts again at the current value, while tracking the best sum seen.

In this guide
  1. Run it: Maximum subarray sum in code
  2. Kadane's algorithm
  3. Tracing it
  4. The one decision
  5. The edge case that catches people
  6. Returning the indices
  7. The all-negative case
  8. Returning the subarray, not just the sum
  9. The variants
  10. Why it is a dynamic programming problem
  11. Sources and next steps

Run it: Maximum subarray sum in code

Kadane with the running values printed at each element. Then the index-tracking version. Then the zero-set up variant getting an all-negative array wrong.

1Python
Output
2Python
Output
3Python
Output

Kadane's algorithm

4Python
Output

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 any follows, so discard it.

The same way:

5Python
Output

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]:

xcurrentbestDecision
−2−2−2Start
111Start fresh — −2+1 = −1 is worse than 1
−3−21Extend (1−3 = −2 beats −3)
444Start fresh
−134Extend
255Extend
166Extend
−516Extend
456Extend

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 apart rather than returned as the final current.

That split is the most common bug: returning current gives the best subarray ending at the last element, not the best total.

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. This 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 cost. 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 apart. 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 starts best to nums[0] rather than to 0.

If an empty subarray is allowed: 0. Then initialise best = 0.

Setting up 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 shows that you spotted the ambiguity.

Returning the subarray, not just the sum

Often the follow-up. Track where the current run started:

6Python
Output

The addition is one variable and one branch. The start moves when 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

ProblemChange
Maximum product subarrayTrack both max and min — a negative times a negative flips
Circular maximum subarrayThe answer is either normal Kadane, or total minus the minimum subarray
At most k elementsSliding window with a deque, or prefix sums
Maximum sum with one deletion allowedTwo DP states: with and without a deletion used
2D maximum submatrixFix a column pair, compress rows, run Kadane — O(n²m)
Longest subarray with sum ≤ kPrefix 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 unneeded. 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.

For the underlying ideas, see dynamic programming, time complexity and divide and conquer.

Sources and next steps

How the code works

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.

How the code works

  1. current = max(v, current + v)The whole algorithm. Either the run continues or it restarts here, and nothing else is ever a candidate for the best subarray ending at this element.
  2. best = max(best, current)Kept separately, because the best run may have ended several elements ago. Collapsing these two variables into one is the most common way to break it.
  3. best = current = values[0]Not zero. Starting at zero silently allows the empty subarray, so an all-negative array returns 0 instead of its least-negative element.
  4. current, start = values[i], iThe index version must record the new start at the moment of the restart, not when the best improves — by then the information is gone.

Change one thing

  • Run [-3, -1, -7] through both versions. The difference is entirely the empty-subarray question.
  • Return the subarray rather than the sum, then check it against max over every slice on a small input.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. At each element, Kadane chooses between:

  2. Initialising best to 0 rather than values[0] breaks:

  3. The space complexity of Kadane is:

Cheat sheet

Maximum subarray sum (Kadane)

Run Kadane's algorithm step by step. Decide at each element whether to extend or restart, and watch the maximum subarray sum update in real time.

INTERVIEW · vizlearn.in/interview/maximum-subarray-kadane.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.