At most k trades, each charged a fee
Asked at Millennium, DE Shaw
Given daily prices, an integer k, and a fee charged on every completed round trip, complete at most k buy-then-sell trades (no overlapping positions) to maximize total profit after fees.
k = 2, prices = [3, 2, 6, 5, 0, 3], fee = 1
-> 5 # buy 2 sell 6 (net 3), buy 0 sell 3 (net 2)
Return the maximum profit.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.