p09 Maximum Subarray — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

Think about walking the array left to right. At each index, you face a yes/no decision: should the optimal subarray ending at this index extend what came before, or start fresh at this element?

Hint 2 — DP state

Let dp[i] = the maximum sum of any contiguous subarray that ends exactly at index i. The global answer is max(dp[i]) over all i. Can you write dp[i] in terms of dp[i-1] and nums[i]?

Hint 3 — The recurrence

dp[i] = max(nums[i], dp[i-1] + nums[i])

Either extend the best subarray ending at i-1 (if doing so beats starting fresh) OR restart at i. Take whichever is larger.

Critical trap: the recurrence is max(nums[i], ...), NOT max(0, ...). The latter is wrong for all-negative arrays — it would return 0, but the problem requires a non-empty subarray.

Hint 4 — Pseudocode skeleton + space collapse

curr = nums[0]                  # dp[i-1]
best = nums[0]                  # global max
for i in 1..N-1:
    curr = max(nums[i], curr + nums[i])
    best = max(best, curr)
return best

Two scalars, not an array. dp[i] only depends on dp[i-1], so a single variable suffices.

Hint 5 — Full algorithm + correctness

Kadane’s algorithm. Walk the array. Maintain two scalars:

  • curr = max sum of any subarray ending exactly at the current index
  • best = max sum of any subarray seen so far

For each new element x:

  1. curr = max(x, curr + x) — extend the previous best or restart at x.
  2. best = max(best, curr) — update running global maximum.

Loop invariant: at the top of iteration i, curr holds the best sum ending at i-1; best holds the global max over all positions 0..i-1. The recurrence preserves both, so after the loop best is the global maximum.

Why all-negative works: for [-3, -2, -1], at i=1: curr = max(-2, -3 + -2) = max(-2, -5) = -2; best = max(-3, -2) = -2. At i=2: curr = max(-1, -2 + -1) = -1; best = -1. Returns -1, the correct answer. The recurrence naturally restarts whenever nums[i] > curr + nums[i], which happens exactly when curr < 0.

Time O(N), space O(1). One pass.

Bonus — divide and conquer (O(N log N)): split in half, recursively find best in left and right halves AND the best subarray crossing the midpoint (linear scan outward from mid). Take max of three. Worse complexity than Kadane on a single machine but generalizes to 2D and parallelizes well.