At most k trades on one price path

Question

You may complete at most k buy-then-sell trades on a price path, never holding two positions at once. Return the maximum total profit. Aim for O(nk), and handle large k specially.

Accepted Answer

Keep buy[j] and sell[j] for j = 1, \dots, k: the best balance while holding your j-th position, and after closing it. Sweep prices once, updating every level. Crucially, when k \geq n/2 the constraint is vacuous (you can never fit more than \lfloor n/2 \rfloor disjoint trades anyway), so just sum every positive day-to-day gain. Tracing [3, 2, 6, 5, 0, 3] with k = 2: sell[1] reaches 4 at price 6 (buy 2, sell 6), and sell[2] reaches 7 at the final price 3 (add buy 0, sell 3). Answer 7. Time O(nk), space O(k). Updating buy[j] before sell[j] within the same price is safe because a same-day buy th…

At most k trades on one price path

Your answer

More Coding questions