DSA problem
Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the i-th day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: i.e. 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.
This is the general form of the buy/sell family. When k = 1 the answer is the classic single-pass max-profit; when k = 2 it is Stock III; and as k grows toward n/2 the constraint becomes inactive — every profitable price climb can be captured because a transaction takes at least two days, so n / 2 transactions is the most that can ever be useful.
The straightforward DP defines dp[t][i][h] where t is the number of transactions used so far, i is the day, and h is whether we currently hold the stock (0 or 1). The transitions are: on day i with t transactions and not holding, either do nothing or buy (dp[t][i][1] candidate); when holding, either do nothing or sell (which finishes one transaction). A full table is O(n * k) cells with O(1) transitions, so O(n * k) total time and space.
The optimal implementation flattens the t dimension into two arrays of length k: buy[t] is the best profit after the t-th buy, and sell[t] is the best profit after the t-th sell. Each day updates them in order t = 1..k using the freshly improved sell[t-1] and buy[t] of the same day. A crucial shortcut: if 2 * k >= n the constraint cannot bite, so fall back to the unlimited-transaction greedy that sums all positive daily deltas. Final answer is sell[k] (or 0 if k = 0).
Examples
k = 2, prices = [2,4,1]2k = 2, prices = [3,2,6,5,0,3]7k = 3, prices = [1,2,3,4,5]4Constraints
- 1 <= k <= 100
- 1 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
- You may not engage in multiple transactions simultaneously.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.