Greedy
When is a local choice safe?
The question the last two units earned you the right to ask, on a problem where the obvious greedy rule is wrong.
Key idea
What greedy means
A greedy algorithm makes the choice that looks best right now and never reconsiders. That is all it means, and it is why greedy code is usually a single pass with no table.
The difficulty is never writing it. It is knowing whether it is correct, because a greedy rule that is wrong still produces plausible answers on small inputs.
A greedy rule that is wrong
You solved the fewest-pieces problem with a table in Unit 14. The obvious greedy rule is to take the largest piece that fits, repeatedly. On ordinary currency it works. On other sets it does not.
Tip
Read those results
For 30 from pieces of 1, 15, and 25, the greedy rule takes the 25 and then five 1s, which is six pieces. Two 15s would have done it in two.
For 6 from 1, 3, and 4, greedy takes a 4 then two 1s, which is three. Two 3s would have done it in two.
Both times the greedy rule commits to a large piece that leaves an awkward remainder. It has no way to notice, because it never reconsiders. That is exactly what makes greedy fast and what makes it dangerous.
Why it works
The argument that makes a greedy rule correct
To justify a greedy choice, use an exchange argument. Assume some optimal solution exists. Show that it can be modified to include your greedy choice without becoming worse. Then an optimal solution containing your choice exists, and the argument repeats on what remains.
You have already seen one. In Unit 6, keeping the interval that finishes earliest was justified by taking any optimal selection, swapping its earliest-finishing interval for the greedy one, and observing that the replacement frees the resource no later, so the rest of the selection stays valid.
That is the shape. If you cannot construct it, the rule is a guess, and a guess that passes the examples in the prompt is the most expensive kind of wrong answer.
Key idea
A greedy decision inside a dynamic programming recurrence
Some problems have a one-line greedy decision that is provably safe, and seeing why is easier now than it would have been six units ago.
Take the largest total obtainable from a contiguous stretch. In Unit 14 terms the state is the best total ending exactly here, and the recurrence has two options: extend the previous stretch, or start fresh at this element.
The greedy observation is that the choice between them needs no table. If the previous stretch's total is negative, extending it can only hurt, so starting fresh is always at least as good. That is a complete exchange argument in one sentence, and it collapses the table to a single running value.
Tip
The two framings agree
You can present this either way. As dynamic programming with the space collapsed, or as a greedy rule with a justification. They produce identical code.
Saying both, and saying that they are the same thing, is a stronger answer than either alone. It is also the reason this unit sits here rather than before Unit 14.
Before writing any greedy solution
State the rule in one sentence. Construct the exchange argument, or admit you cannot. Then look for a counterexample specifically designed to break it, the way the piece sets above were.
If the exchange argument holds, write the single pass. If it does not, you are in Unit 14 territory and need a table.
Which rule can be justified?
You must select the largest possible number of non-overlapping meetings from a list. Which greedy rule has a valid exchange argument?
Maximum Subarray
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.