Free Arrays lessonsArrays · Stage 9 · Kadane’s algorithm · Step 1

Extend or start fresh

Find the largest sum of any run, deciding at each number whether to keep the run going. About 10 minutes.

The best streak ending today

A shop's daily profit and loss: −2, 1, −3, 4, −1, 2, 1, −5, 4. Which run of consecutive days made the most money?

Walk through the days keeping one number: the best total of a streak that ends today. For each new day there are only two options. Either today joins yesterday's streak, or today starts a new streak by itself. Pick whichever total is bigger.

Join or start over: whichever gives the bigger total.

here: best run ending at i

-2

-3

-1

-5

here = −2. best −2.

Move 1 of 8

Let go of a losing streak

If the streak you're carrying has gone negative, adding today to it gives less than today alone. So a negative streak is dead weight: drop it and start fresh.

Keep a second number: the best streak total you've ever seen. That's the answer. If every day was a loss, the best is the least bad single day, so start it at the first day rather than at 0. This walk is called Kadane's algorithm.

Negative streak: drop it: it only drags today down.

All losses? start the best at the first day, not 0.

In code

here = best = nums[0]
for x in nums[1:]:
    here = max(x, here + x)
    best = max(best, here)
return best

Quick check

The best streak ending yesterday totals −4, and today's number is 3. What's the best streak ending today?

A3
B−1
C0

Show the answer

3. −4 + 3 = −1 is worse than 3 alone, so start fresh.

Your problem

Best subarray

You get a non-empty list of numbers. Return the largest sum of a non-empty run of consecutive numbers.

Example

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6

1 ≤ n ≤ 1,000,000 · −10^6 ≤ each value ≤ 10^6 · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.