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

Flip the question

The same walk finds the smallest sum, with max turned into min. About 6 minutes.

The same walk, looking for the worst

Now find the run of days with the smallest total: the worst losing streak. The walk is exactly the same, with the comparison flipped.

The worst streak ending today either continues yesterday's worst streak or starts fresh today. This time a positive streak is the dead weight: carrying it along only makes the total bigger, so drop it.

Continue or start over: whichever gives the smaller total.

Smallest run in [3, -4, 2, -3, -1, 7, -5]

-4

-3

-1

-5

best: 3
here: 3

Start: the only run ending at 3 is [3].

Move 1 of 8

Why you'd want the worst stretch

It sounds like an odd question, but it's a useful tool. If you had to skip one run of days, skipping the worst one leaves you with the most: the total of everything minus the worst stretch.

That trick is exactly what the next step needs, for arrays arranged in a circle. As before, start from the first number, not 0.

Everything minus the worst: is the most you can keep by skipping one stretch.

In code

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

Quick check

Looking for the smallest total: the streak ending yesterday totals 5, and today's number is −2. What's the smallest streak ending today?

A−2
B3
C5

Show the answer

−2. 5 − 2 = 3 is bigger than −2 alone, so start fresh.

Your problem

Smallest subarray

Return the smallest sum of a non-empty run of consecutive numbers in a non-empty list.

Example

nums = [3, -4, 2, -3, -1, 7, -5] → -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.