Skip to content
Back to AlgorithmsAll lessons

Algorithms

Kadane's Algorithm

O(n) time — a single pass through the list · O(1) space.

The idea, in plain English

Kadane's algorithm tracks your running profit day by day. If your running total ever drops below what today alone is worth, you cut your losses and restart counting from today. The whole time, you remember the best streak you have ever had.

How it works

  1. 1Start both the 'current streak' sum and the 'best streak' sum at the value of the first item.
  2. 2At each next item, decide: is it better to extend the current streak, or start a fresh streak here?
  3. 3Update the best streak you have seen so far after every step. Keep going to the end of the list.

When you'd use it

Use it to find the best unbroken run in a sequence — such as the most profitable stretch of stock price changes, or the best streak of gains in a series of ups and downs.

Common beginner mistakes

  • Resetting the current sum to 0 instead of to the current item. This breaks the algorithm when all numbers are negative.
  • Forgetting to update the best sum on every step, not just when you reset.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Numbers: -2 1 -3 4 -1 2 1 -5 4
Max subarray sum: 6

See it in motion

Watch the best streakKadane's algorithmO(n) time — a single pass through the list · O(1) space.

Start the current and best streak at the first value. Press play.

0
Current sum
-1
Best sum
[0, 0]
Best range
0/9
Step
Current cellCurrent streakBest subarrayUntouched

Not sure this is the right topic? See the learning paths → or where this leads →