Best Time to Buy and Sell Stock IV

Problem Maximise profit from at most k non-overlapping buy-sell transactions on a series of daily prices (you must sell before buying again).

Input / Output

• Input: integer k and an integer array prices.
• Output: the maximum achievable profit.

Constraints

• prices up to 1000 long, k up to 100 — but handle k >= n/2 (effectively unlimited transactions) as a special case or the DP blows space needlessly.

Example

• k = 2, prices = [3,2,6,5,0,3] -> 7 (buy 2 sell 6, buy 0 sell 3).