Lesson 3 — Kadane: reset when the past hurts you

~20 minutes · Day 2 · Kadane's algorithm · Python

Tonight's interview pattern is about one question: when is the past worth carrying forward? Maximum Subarray asks for the largest sum from one non-empty contiguous slice. Brute force checks many slices; Kadane turns that search into one left-to-right pass.

The invariant

A running sum that has gone negative can never help a future subarray, so reset it: cur = max(x, cur+x).

That's the whole trick. If the sum before x is negative, adding it to x makes the next candidate worse, not better. So at every number, the best subarray ending here either starts fresh at x, or extends the previous running sum with x.

Kadane asks the same local question at every index: would carrying the previous sum help or hurt?

Maximum Subarray: the slow way first

The problem says the subarray must be contiguous and non-empty (LeetCode). The direct approach is to try every start and extend every possible end:

def max_subarray_slow(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        for right in range(left, len(nums)):   # every slice starting at left
            total += nums[right]
            best = max(best, total)
    return best

This is O(n²): the outer loop chooses a start, and the inner loop walks across the remaining suffix. It works, but the repeated scanning is the waste.

Maximum Subarray: the Kadane way

Kadane keeps two numbers. cur is the best sum ending at the current index. best is the best sum seen anywhere so far. Python's max chooses the larger of two candidates; the algorithm itself is the one-pass maximum subarray method described in the maximum subarray problem.

def max_sub_array(nums):
    best = nums[0]                    # best sum anywhere so far
    cur = nums[0]                     # best sum ending right here
    for i in range(1, len(nums)):
        x = nums[i]
        cur = max(x, cur + x)         # reset, or extend the past
        best = max(best, cur)         # remember the global winner
    return best

Start from nums[0], not 0. If every number is negative, the answer is the least painful single number, not the empty subarray.

The shaded run is not chosen all at once; it appears because cur survives while it helps and best remembers the largest value reached.

Transfer: same question, new costume

A game records daily score changes: [-5, 4, -1, 3, -6, 2]. Find the strongest consecutive run of days. Before reading the reveal, predict the two state variables and the reset rule.

cur = max(x, cur + x)
best = max(best, cur)

What the trade buys you

Practice — answer before you scroll past

best = 0
cur = 0
for x in nums:
    cur = max(x, cur + x)
    best = max(best, cur)

Your move (tonight)

Solve Maximum Subarray in your Notion tracker using the cycle — predict → attempt → compare → encode.

1. Predict: state the brute force and say why a negative running sum should be dropped.
2. Attempt: code Kadane from memory, with cur and best.
3. Compare: watch the source below only after your attempt.
4. Encode: write the invariant in your own words in Notes.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.