Best Time to Buy and Sell Stock IV - Solution & Explanation
Problem Statement
You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3] Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
Approach Overview
Problem Overview: You receive an array prices where prices[i] is the stock price on day i. You may complete at most k buy-sell transactions. Each transaction consists of buying once and selling once. The goal is to compute the maximum profit while respecting the transaction limit.
Approach 1: State-based Dynamic Programming (O(nk) time, O(nk) space)
This method models the problem using explicit DP states. Let dp[t][i] represent the maximum profit achievable using at most t transactions up to day i. For each day, you decide whether to skip trading or sell the stock, which requires tracking the best previous buy opportunity. While iterating through days, maintain a running value like maxDiff = max(dp[t-1][j] - prices[j]) to efficiently compute profits. The approach systematically fills the DP table and clearly illustrates the transaction transitions, making it useful for understanding the classic dynamic programming formulation.
Approach 2: Dynamic Programming with State Compression (O(nk) time, O(k) space)
The DP table can be compressed because each transaction state depends only on the previous transaction layer. Maintain two arrays: buy[t] and sell[t]. buy[t] tracks the best profit after buying for the t-th transaction, and sell[t] tracks the best profit after selling. Iterate through the prices array and update these states sequentially for each transaction count. This reduces memory from O(nk) to O(k) while preserving the same recurrence, making it the preferred implementation in production or interviews. The iteration simply processes each price and updates transaction states using constant-time transitions.
Approach 3: Greedy Optimization for Large k (O(n) time, O(1) space)
If k >= n/2, the constraint effectively disappears because you can perform unlimited transactions. In this case, the optimal strategy is to sum every positive price difference between consecutive days. Iterate once through the array and accumulate max(0, prices[i] - prices[i-1]). This converts the problem into the classic unlimited transaction variant from stock trading problems and avoids unnecessary array DP processing.
Recommended for interviews: Interviewers usually expect the dynamic programming formulation with transaction states. Explaining the full DP table shows understanding of the recurrence. Implementing the state-compressed version demonstrates stronger optimization skills and familiarity with advanced dynamic programming patterns.
Approach 1: Dynamic Programming with State Compression
This approach involves using a dynamic programming table where dp[i][j] represents the maximum profit obtainable on the ith day with up to j transactions. The state can be compressed by keeping track of two main variables: one for the max profit holding deals and one for not holding deals.
We initiate with a check for empty prices array and then determine if we are allowed more transactions than needed for continuous buying and selling. If not, proceed with a reduced number of dynamic programming states constrained by the number of transactions. We update profits using previous profits and manage maximum price differences dynamically.
Complexity
Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions.
Space Complexity: O(n), as we are storing profit states for each day.
Approach 2: State-based Dynamic Programming
This method is a classical dynamic programming solution where we maintain a 2D array dp[j][i], that contains the maximum profit achievable having executed up to j transactions on the ith day.
We use malloc to create a 2D array for storing profit states. The approach involves calculating maximum difference adjustments each time a potential transaction point is evaluated, allowing a full exploration of transaction possibilities up to k times.
Code
C
JavaScript
Complexity
Time Complexity: O(kn).
Space Complexity: O(kn), uses additional space for the DP table.
Approach 3: Memoization Search
We design a function dfs(i, j, k) to represent the maximum profit that can be obtained when starting from day i, completing at most j transactions, and holding the stock with the current state k (not holding the stock is represented by 0, and holding the stock is represented by 1). The answer is dfs(0, k, 0).
The execution logic of the function dfs(i, j, k) is as follows:
- If
iis greater than or equal ton, return0directly. - The i-th day can choose not to do anything, then
dfs(i, j, k) = dfs(i + 1, j, k). - If
k > 0, the i-th day can choose to sell the stock, thendfs(i, j, k) = max(dfs(i + 1, j - 1, 0) + prices[i], dfs(i + 1, j, k)). - Otherwise, if
j > 0, the i-th day can choose to buy the stock, thendfs(i, j, k) = max(dfs(i + 1, j - 1, 1) - prices[i], dfs(i + 1, j, k)).
The value of dfs(i, j, k) is the maximum value of the above three cases.
During the process, we can use memoization search to save the results of each calculation to avoid repeated calculations.
The time complexity is O(n times k), and the space complexity is O(n times k), where n and k are the length of the prices array and the value of k, respectively.
Approach 4: Dynamic Programming
We can also use dynamic programming to define f[i][j][k] as the maximum profit that can be obtained when completing at most j transactions (here we define the number of transactions as the number of purchases), and holding the stock with the current state k on the i-th day. The initial value of f[i][j][k] is 0. The answer is f[n - 1][k][0].
When i = 0, the stock price is prices[0]. For any j \in [1, k], we have f[0][j][1] = -prices[0], which means buying the stock on the 0-th day with a profit of -prices[0].
When i > 0:
- If the i-th day does not hold the stock, it may be that the stock was held on the i-1-th day and sold on the i-th day, or the stock was not held on the i-1-th day and no operation was performed on the i-th day. Therefore, f[i][j][0] = max(f[i - 1][j][1] + prices[i], f[i - 1][j][0])
. - If the i-th day holds the stock, it may be that the stock was not held on the i-1-th day and bought on the i-th day, or the stock was held on the i-1-th day and no operation was performed on the i-th day. Therefore, f[i][j][1] = max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1])
.
Therefore, when i > 0, we can get the state transition equation:
\begin{aligned}
f[i][j][0] &= max(f[i - 1][j][1] + prices[i], f[i - 1][j][0]) \
f[i][j][1] &= max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1])
\end{aligned}
The final answer is f[n - 1][k][0].
The time complexity is O(n times k), and the space complexity is O(n times k), where n and k are the length of the prices array and the value of k, respectively.
We notice that the state f[i][] only depends on the state f[i - 1][], so we can optimize the first dimension of the space and reduce the space complexity to O(k)$.
Approach 5: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Compression | Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions. |
| State-based Dynamic Programming | Time Complexity: O(kn). |
| Memoization Search | — |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| State-based Dynamic Programming | O(nk) | O(nk) | Best for understanding the full DP transition and building intuition |
| DP with State Compression | O(nk) | O(k) | Optimal solution used in interviews and competitive programming |
| Greedy (Unlimited Transactions Case) | O(n) | O(1) | When k >= n/2, reducing the problem to unlimited trades |
Video Solution
Best time to buy and sell stock 4 | Leetcode #188 • Techdose • 29,629 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Best Time to Buy and Sell Stock IV easy or hard?
Best Time to Buy and Sell Stock IV Python/Java solution
How to solve Best Time to Buy and Sell Stock IV in O(n)?
What is the best approach for Best Time to Buy and Sell Stock IV?
Is Best Time to Buy and Sell Stock IV asked at Google/Amazon/Meta?
What data structure is used in Best Time to Buy and Sell Stock IV?
What is the time complexity of Best Time to Buy and Sell Stock IV?
Ready to solve this problem?
Practice Best Time to Buy and Sell Stock IV with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor