Count what you have used
When a limit applies, put how much of it you have used into the table. About 15 minutes.
A limit on the number of trades
Now you may buy and sell, but only k complete trades in total, where a trade is one buy followed by one sell. With k of 1 you pick the best single pair of days. With a bigger k you want the k best ones that don't overlap.
The new difficulty is the limit itself. Before you buy on a given day, you need to know how many trades you have already used, so that number has to be part of what the table remembers.
Two numbers for each trade
For each trade number j from 1 to k, keep two best profits. The first is the profit while you are holding the share you bought for trade j. The second is the profit once trade j is finished and you hold nothing.
Each day, buying for trade j starts from the finished profit of trade j − 1, minus today's price. Selling ends trade j by adding today's price to the holding profit. The answer is the finished profit for k trades.
hold = [-10**9] * (k + 1) done = [0] * (k + 1)
Day 1, price 2. Buying for trade 1 costs 2, so holding is −2. Nothing is finished yet, so both finished rows stay at 0.
With at most 2 trades, you have finished your first trade with a profit of 4. Today's price is 5. What is the holding profit for trade 2 if you buy today?
- A−1
- B−5
- C9
Show the answer
−1. You start from the finished profit of trade 1, which is 4, and pay 5 to buy: 4 − 5 = −1.
At most k trades
You are given an integer k and the price of a share on each day. You may complete at most k trades, where a trade is one buy followed by one sell, and you hold at most one share at a time. Return the largest total profit.
k = 2, prices = [3, 2, 6, 5, 0, 3] → 7
0 ≤ k ≤ 100 · 0 ≤ days ≤ 300 · 1 ≤ price ≤ 1,000