10.33

Idea. Because you may hold at most one share, the only thing that matters is whether the price goes up the next day: every rise can be harvested by buying before it and selling after it. Summing all positive day-to-day differences is therefore optimal.

Algorithm (O(n) time, O(1) space)
profit ← 0 for i = 1 … n – 1 do // 1-based days if G[i+1] > G[i] then output “buy on day i, sell on day i+1” profit ← profit + (G[i+1] – G[i]) return profit and the operations printed above

Why optimal? 1. Suppose G[i+1] > G[i]. Any optimal schedule must own a share on day i and not own it on day i+1, otherwise it misses a sure gain G[i+1] – G[i] > 0.
2. These unit-gains are independent: taking one neither prevents nor forces taking another, because you end each pair of days in the same “no-share” state in which you started.
3. Therefore the total maximum profit is simply the sum of all strictly positive differences G[i+1] – G[i].

Example. G = [7, 1, 5, 3, 6, 4]
Positive jumps: (1→5)=4 and (3→6)=3 → profit = 7.
Operations: buy 2/sell 3, buy 4/sell 5.

The algorithm thus constructs the complete buy–sell sequence and its maximal profit in one left-to-right pass.

Back to Chapter 10