Lesson 16 — Max subarray

Kadane's algorithm: the best stretch

A subarray is a run of neighbouring items. Which run has the biggest sum? Kadane's trick: walk once, keeping cur = the best sum of a run that ends here. At each item, either extend the previous run (cur + x) or start fresh at x — whichever is bigger. Track the overall best.

run = max(item, run + item)   # start fresh, or extend
top = max(top, run)           # remember the best so far

Why it matters: "best profit window" or "strongest streak" questions are solved in one O(n) pass instead of checking every pair of start and end.