AlgoScope

Maximum Subarray (DP view)

best-ending-here(i) = max(a[i], best-ending-here(i-1) + a[i]).

Dynamic programming, algorithm, intermediate
Position 1: the best run ending here is 1. The best overall is 1.active 1-1-2011-3243-142516-5748i
Position 1: the best run ending here is 1. The best overall is 1.active 1-1-2011-3243-142516-5748i

DP in One Row: Maximum subarray

Decision, step 2 of 10

Value 1. Extending the run gives -1, restarting gives 1. The old run only hurts, so restart: dp[1] = 1. New best, 1.

How dp in one row works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

A variant of

Taught by the same lesson

DP in One Row covers these too, in the same run.