Maximum Subarray — The Busker's Ledger

Boss 1: The Busker's Ledger

Welcome to Dungeon 14. Thirteen dungeons in, you've built machines: heaps, DP tables, graph traversals. Greedy is the anti-machine. A greedy algorithm makes the locally best choice at every step and never looks back, no memo table, no backtracking. When that works, and proving when is the whole art, the code shrinks to a loop.

This first boss is the friendliest possible introduction, because you've already brushed against it. Dungeon 12's Hot Streak (Maximum Product Subarray) name-dropped Kadane's algorithm. Today you fight the original.

The story

Every evening you play guitar on the same corner. The city charges a pitch fee, tips vary wildly, and your ledger for the last nine nights reads:

night:    1    2    3    4    5    6    7    8    9
profit:  -2    1   -3    4   -1    2    1   -5    4

A festival organizer asks: "What's your best run?" Not your best single night. Your best consecutive stretch, total profit, because that's what a residency would look like.

Eyeball it: nights 4 through 7 give 4 - 1 + 2 + 1 = 6. Nothing beats that. But eyeballing doesn't scale to a year of ledgers, so you need the rule behind the answer.

The problem, dressed up properly

Given an integer array nums, find the subarray with the largest sum, and return its sum.

LeetCode 53. The most classic "greedy or DP?" problem in existence, and the answer is: it's both, wearing different hats.

The naive attempt

Try every stretch. Fix a start night, extend the end night, track the best total:

def max_subarray(nums):
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            best = max(best, total)
    return best

O(n²). For nine nights, fine. For a decade of busking, you'll finish computing around the time you retire. The waste is obvious once you see it: the run starting at night 1 and the run starting at night 2 share almost all their work, and we redo it anyway.

The weapon: drop the ledger when it goes negative

Walk the nights once, carrying a single running total: the best sum of any run ending right here.

At each night you face one choice. Either extend the run you're carrying, or abandon it and start fresh from today. When is abandoning correct? Exactly when the carried total is negative. A negative prefix can only drag down whatever comes next. Nobody straps a losing streak to their back on purpose.

That's the greedy insight in one line: a negative running total is dead weight, and dead weight gets dropped immediately.

def max_subarray(nums: list[int]) -> int:
    best = cur = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)   # extend the run, or start fresh here
        best = max(best, cur)   # remember the best run seen anywhere
    return best

Four lines of logic. This is Kadane's algorithm, and max(n, cur + n) is the entire decision: if cur is negative, n alone wins and the run restarts.

Watching it work

The ledger again: [-2, 1, -3, 4, -1, 2, 1, -5, 4].

night  profit   cur (run ending here)        best
1        -2     -2                            -2
2         1     max(1, -2+1)  = 1  restart     1
3        -3     max(-3, 1-3)  = -2 extend      1
4         4     max(4, -2+4)  = 4  restart     4
5        -1     max(-1, 4-1)  = 3  extend      4
6         2     max(2, 3+2)   = 5  extend      5
7         1     max(1, 5+1)   = 6  extend      6
8        -5     max(-5, 6-5)  = 1  extend      6
9         4     max(4, 1+4)   = 5  extend      6

Answer: 6, nights 4 through 7, found in one pass. Notice night 8: the run takes a -5 hit but stays positive at 1, so we keep carrying it. It never recovers past 6, but the algorithm didn't know that yet, and keeping a positive total is always safe.

Gotchas

1. Initializing best to 0. On an all-negative ledger like [-3, -1, -2] the answer is -1, the least-bad night. Start best at 0 and you'll return 0, claiming an empty run, which the problem forbids. Initialize both best and cur to nums[0].

2. Restarting on any loss instead of a negative total. Night 5 loses money, but the carried total 3 is still positive, still worth strapping on. You restart when the total goes negative, not when a single night does. Tempting shortcut, wrong answer.

3. Forgetting the answer can end anywhere. cur tracks the best run ending now. The overall best might have ended three nights ago, which is why best is a separate variable updated every step, not read once at the end.

4. Trying to return the subarray itself with no extra bookkeeping. The sum needs two variables. The actual start and end nights need you to record the index whenever a restart happens and whenever best improves. Interviewers love this follow-up, so wire it up once at home.

Complexity

One pass, two variables.

Time: O(n). Space: O(1).

Boss down. XP gained.

The organizer gets a clean answer: nights 4 to 7, profit 6, residency earned. The ledger goes back in the guitar case.

What you walked away with:

• The greedy reflex: make the local choice that can never hurt you, here dropping negative prefixes
• max(n, cur + n) is "extend or restart" compressed into one expression
• Kadane is greedy and DP simultaneously, a nice thing to say out loud in interviews
• All-negative arrays are the classic edge case: initialize from nums[0], never 0

Next up: Boss 2 — The Creek Crossing. Stepping stones across a creek, each stone tells you how far it can launch you, and one question: can you reach the far bank at all? First appearance of the reach trick, greedy's favorite tool.