259. Maximum Profit with k Transactions

Hard · Dynamic Programming

You have an array of stock prices and may complete at most `k` transactions. A transaction is one buy + one sell. Maximise profit. You cannot hold more than one share at a time.

Examples

Example 1
Input: k=2, prices=[3,2,6,5,0,3]
Output: 7
Explanation: Buy at 2, sell at 6 (+4). Buy at 0, sell at 3 (+3). Total=7

Constraints

• 1 ≤ k ≤ 100, 1 ≤ n ≤ 1000, 0 ≤ prices[i] ≤ 1000