Best Time to Buy and Sell Stock IV

The key idea

Carry, for each transaction slot t, the best running buy[t] (most cash-positive position after buying the t-th stock) and sell[t] (best profit after selling it). For each day, buy[t] improves to sell[t-1] - price (fund this buy from the prior sale's profit) and sell[t] improves to buy[t] + price. The answer is sell[k].

Problem

You are given an integer k and an integer array prices where prices[i] is the price of a given stock on the i-th day.

Find the maximum profit you can achieve. You may complete at most k transactions: you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously — you must sell the stock before you buy again.

Constraints

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

Examples

Input: k = 2, prices = [2,4,1] Output: 2

Input: k = 2, prices = [3,2,6,5,0,3] Output: 7

Complexity

Time: O(n*k) Space: O(k)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →