Best profit with at most k trades
Asked at Millennium, DE Shaw
Given daily prices and an integer k, complete at most k buy-then-sell trades (you must sell before buying again, no overlapping positions) to maximize total profit.
k = 2, prices = [3,3,5,0,0,3,1,4] -> 6 # buy 0 sell 3, then buy 1 sell 4
k = 2, prices = [1,2,4,2,5,7,2,4,9,0] -> 13
Return the maximum profit. This is the general case of the one-trade and two-trade problems.
Show a hint
Track, for each transaction count j from 1 to k, two states: the best balance while holding your j-th position, and the best profit after closing it. Update them price by price. Also: what happens when k is so large it never binds?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.