cf.completefrontend
ARRAYS & HASHING · CORE

Kadane's algorithm

Find the largest sum of any run of neighboring numbers in one pass, by deciding at each number whether to extend the current run or start fresh.

Time O(n)Space O(1)8 practice problemsStep-through picture

The idea

Given a list of numbers that can be positive or negative, which run of neighboring numbers (a subarray) has the largest sum? Checking every start and end takes O(n^2) time. Kadane's algorithm does it in one pass.

Walk through the numbers keeping current: the best sum of a run that ends exactly at this number. For each new number there are only two choices: add it to the run that ended just before (current + nums[i]), or start a new run with just this number (nums[i]). Pick the bigger one. If the run so far has a negative sum, it can only drag the new number down, so starting fresh wins.

Alongside current, keep best: the largest current seen anywhere. When the walk ends, best is the answer.

An everyday example

A hiking streak

You log how many meters you climb each hour of a hike; negative numbers mean you went downhill. You want the stretch of hours with the biggest total climb. As you go, you track the climb of the stretch you're in. If that stretch has become a net loss, carrying it forward can only hurt, so you start counting a new stretch from this hour. You also write down the best stretch total you've ever reached.

How the example maps to the code
In the exampleIn the code
Your current stretch's total climbcurrent
Dropping a stretch that has become a net lossMath.max(nums[i], current + nums[i]) picks nums[i]
The best stretch total written in your notebookbest
Checking the notebook after each hourbest = Math.max(best, current)

From the slow way to kadane's algorithm

  1. The obvious way to find the largest sum of neighboring numbers: try every start, extend the end one step at a time, and keep a running sum. That is about n² / 2 subarrays. For 100,000 daily values, it's 5 billion steps.
  2. Group the subarrays by where they end. For each end i, find the best subarray ending exactly at i. Every subarray ends somewhere, so the overall answer is the largest of these n best-ending-here values.
  3. Now the key fact: the best subarray ending at i is either nums[i] alone, or nums[i] added to some subarray ending at i - 1. If it's the second kind, it should use the best subarray ending at i - 1, since any weaker one gives a smaller total. So each step needs only one number from the step before.
  4. Keep that number as current, and keep best, the largest current so far. At each number choose the larger of "start fresh" and "extend", then update best. One pass and two variables: that loop is Kadane's algorithm.

How it works

  1. Set current and best to nums[0]: the only run ending at index 0 is the first number itself.
  2. Walk i from 1 to the end.
  3. The best run ending at i either extends the previous one or starts fresh: current = Math.max(nums[i], current + nums[i]).
  4. If this run beats every run before, record it: best = Math.max(best, current).
  5. After the loop, return best.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function maxSubarraySum(nums) {
  2. let current = nums[0];
  3. let best = nums[0];
  4. for (let i = 1; i < nums.length; i++) {
  5. current = Math.max(nums[i], current + nums[i]);
  6. best = Math.max(best, current);
  7. }
  8. return best;
  9. }

How fast it is

TimeO(n)
Extra memoryO(1)

One pass, with two Math.max calls per number. Only current and best are stored.

  • Best caseO(n)

    There's no early exit. Even an all-positive list, where every step extends, visits all n - 1 remaining numbers.

  • Average caseO(n)

    One pass with two Math.max calls per number.

  • Worst caseO(n)

    No input is slower: a list that restarts at every number costs the same as one that never restarts.

Common mistakes

  • Starting best at 0, which returns 0 for an all-negative list instead of its largest number.
  • Resetting current to 0 when it goes negative and allowing empty runs, when the problem asks for at least one number.
  • Using it for the largest product without tracking the smallest product too; two negatives multiply into a big positive.
  • Updating best before updating current, which compares against the previous position's run.

When to use it

Look for these clues in a problem:

  • The problem asks for the largest (or smallest) sum of a contiguous run: a subarray, a streak, a stretch of days.
  • The numbers can be negative, so you can't just take everything.
  • The answer depends on the best run ending at each position, built from the best run ending at the previous one.
  • Variations: the largest product, a circular array, or allowing one item to be skipped.

Check yourself

Answer each one in your head first, then open it.

In the trace, why does the run keep -1 and -2 instead of restarting after them?

The run's sum stays positive (3, then 1), so carrying it forward helps the next number. Restarting only wins when the run's sum is negative.

At nums[5] = -7, why is current set to -1 even though it's negative?

current must describe a run that ends at index 5. The choices are -7 alone or -1, and -1 is larger. best still remembers 6.

What does [5, -9, 6] return?

6. At -9, current is max(-9, -4) = -4. At 6, it's max(6, 2) = 6, which becomes best.

Why is this called dynamic programming?

Each step's answer, the best run ending here, is built from the answer to the smaller problem one step back, and each smaller answer is computed once.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps two promises. After handling index i, current is the largest sum of a subarray that ends exactly at i, and best is the largest sum of any subarray that ends at or before i. At index 0 the only subarray is [nums[0]], so starting both at nums[0] is right.

The step keeps the first promise because of optimal substructure: the best answer is built from the best answer to a smaller question. A best subarray ending at i with more than one number is a subarray ending at i - 1 plus nums[i]. If that front part weren't the best one ending at i - 1, swapping in the best one would give a bigger total. So Math.max(nums[i], current + nums[i]) covers every candidate.

best then takes the larger of itself and the new current, which keeps the second promise. The values are filled left to right because each one needs only the one before it, and that's why only one number has to be stored. When the loop ends, every possible end has been covered, so best is the answer.

Going deeper

3 more ideas

Why two choices are enough

Any run ending at index i is either nums[i] alone or some run ending at i - 1 with nums[i] added. The best of the second kind uses the best run ending at i - 1, which is current. So Math.max(nums[i], current + nums[i]) is the best run ending at i. Every subarray ends somewhere, so the largest current over all positions is the answer. This makes Kadane's algorithm a tiny dynamic programming solution.

When every number is negative

Starting current and best at nums[0] (not 0) matters. For [-4, -2, -7] the right answer is -2, the single least negative number. If best started at 0, the code would return 0, which is the sum of an empty run, and most problems don't allow that.

Variations

To also return where the best run is, remember the index where current last started fresh and copy it when best improves. For the largest product, track both the largest and smallest product ending here, since a negative times a negative becomes positive. For a circular array, the answer is either the normal best or the total minus the smallest run.

Work it by hand

Every step in a table, with why

Find the largest subarray sum in 7 numbers. The winning run passes through two negative numbers, and the last step starts fresh without beating best.

nums = [-3, 4, -1, -2, 5, -7, 2]

Stepinums[i]current + nums[i]currentbestChoiceWhy
1--3--3-3Start at nums[0]Both variables start at the first number, not 0, so an all-negative list still gives a real answer.
214144Start fresh: 4 > 1The run so far is negative, so it can only drag 4 down. Starting a new run at 4 wins.
32-1334Extend: 3 > -1A negative number, but the run [4, -1] still sums to 3, better than -1 alone.
43-2114Extend: 1 > -2Another negative. The run [4, -1, -2] is still positive, so it is kept for what comes next.
545666Extend: 6 > 5, new bestKeeping the run pays off: 1 + 5 = 6 beats 5 alone. best becomes 6.
65-7-1-16Extend: -1 > -7The run must end at index 5, and -1 is better than -7 alone. best keeps 6.
762126Start fresh: 2 > 1The negative run is dropped. current is 2, which doesn't beat best.

It returns 6, from the run [4, -1, -2, 5] at indexes 1 to 4. The loop ends because every number was used as an end once.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Kadane's algorithmO(n)O(1)The default for the largest-sum subarray, in one pass with no extra memory.
Running totals: subtract the smallest earlier totalO(n)O(1)You already think in prefix sums. The best sum ending at i is the total so far minus the smallest earlier total.
Divide and conquerO(n log n)O(log n)You need to combine answers from halves, as in a segment tree that answers the question for any range.
Every start with a running sumO(n²)O(1)Small inputs, or when the problem adds rules that Kadane's two choices can't express.

Extra memory: O(1): just current and best, whatever the list's length.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Kadane's algorithm and the other approaches, on a scale where each line up is 10 times more steps.
  • Kadane's algorithm, Running totals: subtract the smallest earlier total O(n)
  • Divide and conquer O(n log n)
  • Every start with a running sum O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Kadane's algorithm101,0001 million
Running totals: subtract the smallest earlier total101,0001 million
Divide and conquer339,96620 million
Every start with a running sum1001 million1 trillion

Inputs that need care

5 tricky inputs
One number: nums = [-8]
The loop doesn't run, and it returns -8.
All negative: nums = [-6, -2, -9]
It returns -2, the least negative single number. This works only because best starts at nums[0] and not 0.
An empty list: nums = []
nums[0] is undefined, and it returns undefined. Decide what an empty list should give, such as 0 or an error, and check for it first.
Zeros: nums = [0, -1, 0]
It returns 0. Many runs tie at 0, and any of them is a correct answer.
Ties: nums = [3, -3, 3]
best is 3, reached by [3], [3, -3, 3], and the last [3]. If you also return positions, decide which one a tie should report.

Variations and follow-ups

Twists interviewers add

One deletion allowed

Keep two values per position: the best run ending here with no deletion, and the best with one deletion. The second is either the first value from the step before (delete this number) or the second value plus this number. Both update in constant time.

Best single buy and sell

The best profit from buying on one day and selling on a later day equals the largest subarray sum of the daily price changes, price[i] - price[i - 1], or 0 if every change is negative.

Largest-sum rectangle in a grid

Fix a top row and a bottom row, add up each column between them into one list, and run Kadane's algorithm on that list. This tries every row pair in O(rows² × cols).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "maximum sum of a contiguous subarray", "best run", or "largest gain over a stretch of days".
  • Say the state out loud: "current is the best sum of a run that ends exactly here." Then the choice between extending and restarting is easy to defend.
  • Test by hand: all negative numbers, a single number, and a list where the best run crosses a negative number.
  • The usual follow-up is the circular version. Answer: the best is either the normal answer or the total minus the smallest subarray sum, except when every number is negative, where the normal answer is right.

Where frontend code uses it

The same idea in real UI code
  • A stock or crypto price widget can show the best buy-then-sell window by running Kadane's algorithm on day-to-day price changes.
  • Analytics dashboards highlight the stretch of days with the largest net growth (sign-ups minus cancellations).
  • Picking the strongest stretch of a signal, such as the loudest span of an audio waveform drawn in the browser.

Related algorithms