Kadane (best ending here)

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Daily profits of a small shop over nine days: −2, 1, −3, 4, −1, 2, 1, −5, 4. Which stretch of consecutive days earned the most in total? By hand you add up stretches: days 4 to 7 give 4 − 1 + 2 + 1 = 6; days 4 to 9 give 6 − 5 + 4 = 5; day 9 alone gives 4. The best is 6.

How many stretches are there? Any start day and any end day on or after it: for 9 days that is 45 stretches, and for n days about n²/2. Adding each one up costs up to n more, so about n³/6 additions, or 166 billion for a million days. Even with running sums it is 500 billion stretches to compare.

Build the structure, one piece at a time

Piece one: a different question. Instead of "best stretch anywhere", ask "best stretch that ends exactly on day i". Call it cur[i].

Piece two: the observation that makes the question easy. A stretch ending on day i either is day i alone, or is a stretch ending on day i − 1 with day i added. The best of the second kind is cur[i − 1] + nums[i]. So

cur[i] = max( nums[i], cur[i − 1] + nums[i] )

In words: extend the run if the run so far is positive, otherwise start fresh at day i, because a run that has gone negative only drags you down.

Piece three: a single number best that remembers the largest cur seen.

On day 2, cur[1] = −2 is negative, so cur[2] restarts at 1. On day 4 the same: −2 + 4 = 2 is worse than 4 alone.

Why it is correct

The invariant: cur is the maximum total of any stretch ending exactly at the current day. The two-case argument above shows the formula computes it from the previous day's value, and day 1 is trivially right. Every stretch ends on some day, so the best overall is the maximum of cur over all days, which is what best tracks.

The mathematical heart: if cur[i − 1] < 0 then cur[i − 1] + nums[i] < nums[i], so a negative prefix can never help, and dropping it is always safe.

Why it is fast

One max and one addition per day:

work = n, memory = 2 numbers

A million days cost a million steps instead of hundreds of billions.

How to recognise it in an interview

Cues: "contiguous subarray", "maximum sum", "best stretch", "buy on one day and sell on a later day". The first thing to say: "track the best run ending here, restart when it goes negative." Maximum Subarray is the example above. Best Time to Buy and Sell Stock is Kadane on the day-to-day price differences, since a buy-sell profit is the sum of consecutive differences. Maximum Product Subarray needs the same idea with two runs, best and worst, because a negative times a negative becomes the new best.

02The idea in one line

best ending at i = max(nums[i], best ending at i−1 + nums[i]).

Reach for it when: Maximum subarray, max product subarray, max circular subarray, stock I.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Maximum Subarray on [-2,1,-3,4,-1,2,1,-5,4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. cur = max(nums[i], cur + nums[i]): extend the run or restart at i
2. i = 0: start, cur = -2, best = -2
3. i = 1: restart, cur = 1, best = 1
4. i = 2: extend, cur = -2
5. i = 3: restart, cur = 4, best = 4
6. i = 4: extend, cur = 3
7. i = 5: extend, cur = 5, best = 5
8. i = 6: extend, cur = 6, best = 6
9. i = 7: extend, cur = 1
10. i = 8: extend, cur = 5
11. Best = 6 from the run [4,−1,2,1]
12. A negative prefix never helps, so drop it: O(n) time, O(1) space

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).