Where it runs
1. The problem
Greedy goes wrong when the best choice right now spoils the best overall result. Dynamic programming helps then. You split the task into small subtasks that share work. You solve each one once and later take its answer ready-made.
You have a row of daily numbers: the money made each day. Some days had refunds, so the number goes below zero. Finance asks: which few days in a row made the most money together? The answer can be a single day or the whole month, but usually it is a stretch somewhere in between.
The slow way: try every start and every end, and add up every stretch. On one month that is fine. On years of data it is the O(n2) trap you learned to spot back at lesson 09.
You can answer this question in one pass. The method that gives it makes many scary-looking problems simple. That method is the topic of this lesson.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmaxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5])Find the largest sum of a contiguous stretch. The state at i is the best sum of a run that ends exactly at i.
Bars: how many times the answer for each stair i was computed, i from 0 to 18.
One operation is one call or one table cell. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- best/maximum/minimum ending at position i
- ways to reach, climb, or tile
- cannot pick two adjacent items
- minimum cost path through a grid
- overlapping subproblems, same state recomputed
Looks similar, isn't
- Recursion with memoization
Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
- Greedy (exchange argument)
Greedy commits to one choice per step. DP keeps every option until the end.
- Recursion
The recursion tells you what the transition is. The table is what makes it fast.
- DP on subsequences (LIS / LCS / edit distance)
There the state is a pair of positions in two sequences. Here one index is enough.
n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.
On LeetCode
Problems where the best answer at position i depends only on the answers one or two positions back, such as robbing houses, climbing stairs or the best run ending here. Two running numbers replace the whole table.
Each step costs the cheaper of coming from one or two steps below, plus its own price.
The lesson's maxSubArray. At each number extend the run or start fresh.
The lesson's rob, with take and skip carried in two numbers.
The houses form a circle, so run rob twice, once without the first house and once without the last, and keep the larger.
Sum the points for each value, then run rob over the values, since taking v costs you v minus 1 and v plus 1.