prices[i] is the price of one share on day i. A trade is buying one share and selling it on a later day; its profit is the selling price minus the buying price. You may make at most k trades, and you hold at most one share at a time, so each share must be sold before the next one is bought. Selling one share and buying the next on the same day is allowed.
Write max_profit_k_trades(k: int, prices: list[int]) -> int that returns the largest total profit. Making no trade at all earns 0.
Examples, all with prices = [1, 6, 4, 9, 2, 5]:
max_profit_k_trades(1, prices) == 8: buy at 1, sell at 9.max_profit_k_trades(2, prices) == 11: buy at 1, sell at 9, then buy at 2, sell at 5. The two biggest single rises, 1 to 6 and 4 to 9, only make 5 + 5 = 10.
max_profit_k_trades(3, prices) == 13: take every rise, 5 + 5 + 3.max_profit_k_trades(10, prices) == 13: there are no more rises to take, so extra trades don't help.max_profit_k_trades(0, prices) == 0andmax_profit_k_trades(4, []) == 0.
Constraints: 0 <= k <= 10^5, 0 <= len(prices) <= 2000, 0 <= prices[i] <= 10^4.
⭐ Bonus: speed tests with 2,000 days earn a star, one with k = 500 and one with k = 100,000. A table of n·k states is fine for the first, but for the second it's 200 million steps. Think about how many trades can ever be useful.
Show hint
Keep two numbers per trade count j: the best cash while holding the j-th share, and the best cash after j trades. Each day, update them for j = 1..k, the way you would for two trades. And a trade that makes money needs a buy day and a later sell day, so n days can't fit more than n // 2 of them.