Maximum Subarray (DP view)
best-ending-here(i) = max(a[i], best-ending-here(i-1) + a[i]).
DP 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.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
A variant of
Taught by the same lesson
DP in One Row covers these too, in the same run.