Maximum Subarray (DP view)
best-ending-here(i) = max(a[i], best-ending-here(i-1) + a[i]).
Decision · step 2 of 10DP in One Row: Maximum subarray
Value 1. Extending the run gives -1, restarting gives 1. The old run only hurts, so restart: dp[1] = 1. New best, 1.
What you will see
One row of states; the running best resets when it would go negative.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
A variant of
Taught by the same lesson
DP in One Row covers these too, in the same run.