vizlearn

Maximum subarray sum (Kadane)

Interview QuestionsBy Updated

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.

Overview

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.

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."

Maximum subarray sum (Kadane)

Find the contiguous subarray with the largest sum.

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.

Run it in Python

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.pyPython 3
Output
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)
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.
INTERVIEW · vizlearn.in/interview/maximum-subarray-kadane.html
More in Interview
InterviewRemove duplicates from a sorted array in placeInterviewRotate an array by kInterviewProduct of array except selfInterviewHow does a Python dict work?
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.
About VizLearnGitHubLinkedInContact