Best Profit With at Most K Trades
You know the price of a token for each day in prices. A trade means buying one token on some day and selling it on a later day. You may make at most k trades and can hold at most one token at a time (you must sell before buying again; selling and buying on the same day is allowed).
Return the maximum total profit. If no trade is profitable, return 0.
Example 1
Input: k = 2, prices = [1,5,2,8,3,10] Output: 14 Explanation: Buy at 1, sell at 8; buy at 3, sell at 10.
Example 2
Input: k = 1, prices = [7,6,4,3,1] Output: 0 Explanation: Prices only fall.
Constraints
- 0 <= k <= 100
- 0 <= prices.length <= 10^4
- 0 <= prices[i] <= 1000
Hint 1
Track, for each j, the best balance while holding a token in trade j and the best balance after completing j trades.
Hint 2
If k is at least half the number of days, the limit never binds: take every rising step.
Discussion 0
Join free to post in the discussion.
Good practice for: Data Scientist, Backend Developer, Blockchain Developer, Machine Learning Engineer, Data Engineer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.