Greedy vs Dynamic Programming

A greedy algorithm commits to one choice at each step and never revises it, usually picking the locally best option. It works when that local choice can never hurt the final answer, which is a property you have to prove rather than assume. A dynamic program keeps the best answer for every state and combines them, which is what you need when a locally attractive choice can rule out a better global outcome.

def max_profit(prices):
    lowest = prices[0]
    best = 0
    for price in prices[1:]:
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best


print(max_profit([7, 1, 5, 3, 6, 4]))

The output is 5, which is the profit from buying at one and selling at six.

The mechanism is that keeping the lowest price seen so far is always safe, because any future sale can use that lowest price no matter when it happens. There is no state that has to be remembered beyond that one value, so there is nothing for a dynamic program to combine.

The trade-off to name is the proof burden. Greedy is faster and uses less space, usually linear time and constant space, but you are betting on the problem's structure. When the exchange argument does not hold, greedy silently produces a wrong answer, and that is exactly what the interviewer is testing when they offer both variants of a problem. The other point is that a dynamic program is often the safer default, since it works whenever the local choice is safe and the cost is only a bigger table.

Keep a table where each entry holds the best profit achievable up to that price, combining the answer from the previous entry with the best sale at that price.

def max_profit(prices):
    if not prices:
        return 0
    best = [0] * len(prices)
    lowest = prices[0]
    for i in range(1, len(prices)):
        best[i] = max(best[i - 1], prices[i] - lowest)
        lowest = min(lowest, prices[i])
    return best[-1]


print(max_profit([7, 1, 5, 3, 6, 4]))

The output is 5, the same as the greedy version produced.

The mechanism is that the table records the best profit up to each position, and each entry either extends the previous best or takes the profit from selling at the current price. The extra state is what makes it a dynamic program: it could, in principle, carry more than one piece of information per position.

The trade-off to name is that this version keeps the whole history in the table, using space linear in the number of prices, while the greedy version keeps only the running minimum and uses constant space. Here the two are equivalent because the greedy choice is genuinely safe, which is the usual outcome when a problem has a simple greedy solution. The interesting cases are the ones where greedy fails, such as the coin change problem with an arbitrary coin set, and that is worth mentioning to show you know the boundary.

The standard proof is an exchange argument. You identify the choice your greedy algorithm makes, and you show that there is always an optimal solution that contains that choice. Then you argue that the same holds for the remaining problem, so by induction the greedy solution is optimal.

Concretely, for a problem with several subproblems you often prove a cut or partition property: take the lightest edge of the whole graph and show it belongs to some minimum spanning tree, because the lightest edge crossing any cut is safe. The same shape of argument works for interval scheduling, where you take the earliest finishing interval and show that it can be swapped into any optimal schedule without making it worse.

The proof has to be stated, because a greedy algorithm that happens to work is not the same as one that is guaranteed to work. Interviewers are usually watching for exactly this: whether you can say why the local choice cannot hurt, rather than asserting that it is obviously best.

The trade-off to name is that the proof is often the hard part of the interview question and the code is five lines. Where you cannot produce the exchange argument, the safe move is to fall back on a dynamic program, which is slower but correct under weaker assumptions. There is also a subtlety about ties: when several choices are equally good locally, a greedy algorithm may need a tie-breaking rule, and choosing badly among equals can break the overall optimality even though each individual choice looked fine.