67. Best Time to Buy and Sell Stock IV

Hard · Dynamic Programming

You are given a list of stock prices and a maximum number of transactions you're allowed to make. A transaction consists of buying and then selling one share. You must sell before you can buy again, and you cannot hold multiple shares at once. Find the maximum profit you can achieve with at most k transactions. If you cannot make any profit, return 0. The input is [k, prices] where k is the maximum number of transactions allowed and prices is an array of integers representing the stock price on each day.

Examples

Example 1
Input: [2, [2,4,1]]
Output: 2
Explanation: Buy at 2 sell at 4 = 2; no second beneficial trade
Example 2
Input: [2, [3,2,6,5,0,3]]
Output: 7
Explanation: Buy 2 sell 6 (+4), buy 0 sell 3 (+3)

Constraints