Best Time to Buy and Sell Stock II
Greedy: bank every upward step
With unlimited trades there is no decision to agonise over. Any profitable run from a low day to a high day pays exactly the sum of the day-to-day rises inside it, because selling and immediately rebuying at the same price costs nothing. So the whole problem collapses to one sweep: add every positive difference between consecutive days and ignore every negative one. No running minimum, no lookahead, no dynamic programming — a fall simply cannot be worth holding through, since you are free to sell before it.
Details
Animated on: prices = [4,2,6,5,9,9,1,7] — buy and sell as many times as you like (never holding two lots at once) for the maximum total profit.
Problem:Best Time to Buy and Sell Stock IIMedium
Greedy: bank every upward step
step 1 / 9
Unlimited trades means the days are independent: any profitable run from a low to a high equals the sum of its day-to-day rises, so there is nothing to plan ahead for. profit starts at 0 and every upward step gets banked on its own.
1FUNCTION maxProfit(prices)2 profit <- 03 FOR i <- 1 TO LENGTH(prices) - 14 IF prices[i] > prices[i - 1]5 profit <- profit + prices[i] - prices[i - 1]6 RETURN profit
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Unlimited trades means the days are independent: any profitable run from a low to a high equals the sum of its day-to-day rises, so there is nothing to plan ahead for. profit starts at 0 and every upward step gets banked on its own.
- Day 1 falls to 2 from 4, a loss of 2. Nobody is forced to hold a stock, so this drop is simply skipped instead of dragging an earlier gain down; profit stays 0.
- Day 2 costs 6, up from 2 the day before, so buying at 2 and selling at 6 banks 4. Holding through a longer climb would earn exactly the same total, so taking the step here loses nothing. profit is now 4.
- Day 3 falls to 5 from 6, a loss of 1. Nobody is forced to hold a stock, so this drop is simply skipped instead of dragging an earlier gain down; profit stays 4.
- Day 4 costs 9, up from 5 the day before, so buying at 5 and selling at 9 banks 4. Holding through a longer climb would earn exactly the same total, so taking the step here loses nothing. profit is now 8.
- Day 5 is still 9, unchanged from the day before, so a trade across it would earn 0. The test is strictly greater, so nothing is banked — profit stays 8.
- Day 6 falls to 1 from 9, a loss of 8. Nobody is forced to hold a stock, so this drop is simply skipped instead of dragging an earlier gain down; profit stays 8.
- Day 7 costs 7, up from 1 the day before, so buying at 1 and selling at 7 banks 6. Holding through a longer climb would earn exactly the same total, so taking the step here loses nothing. profit is now 14.
- Every rise has been banked and every fall skipped: 6 of the 8 days end up inside a trade and the total is 14. The single-transaction version of this problem needs a running minimum precisely because it may bank only ONE rise — with unlimited trades that bookkeeping disappears.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.