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] <= 1000Problem Overview: You are given an array of daily stock prices and an integer k. You can complete at most k buy-sell transactions. The goal is to maximize total profit. You cannot hold multiple stocks at once, so every buy must be followed by a sell before the next transaction.
Approach 1: State-based Dynamic Programming (O(n * k) time, O(n * k) space)
This approach models the problem using explicit DP states for each day and transaction count. Define dp[i][j][0] as the maximum profit on day i after completing j transactions and not holding a stock, and dp[i][j][1] as the profit while holding a stock. For each day, transition between states by either skipping the day, buying, or selling. The buy operation transitions from dp[i-1][j-1][0] to dp[i][j][1], while the sell operation moves from dp[i-1][j][1] to dp[i][j][0]. Iterating through the array of prices and updating these states builds the optimal solution. This method is easy to reason about because it mirrors the trading process directly.
Approach 2: Dynamic Programming with State Compression (O(n * k) time, O(k) space)
The full DP table is not necessary because each state only depends on the previous day. Compress the DP into two arrays: buy[j] and sell[j], representing the best profit after the j-th buy or sell. Iterate through prices and update these arrays in order of transactions. The key insight is that every transaction consists of a buy followed by a sell, so the algorithm tracks the best possible state after each step. This reduces memory usage from O(n * k) to O(k) while keeping the same O(n * k) time complexity. This is the standard optimization used in many dynamic programming stock problems.
Optimization: Greedy when k ≥ n/2 (O(n) time, O(1) space)
If k is large relative to the number of days, the transaction limit effectively disappears. When k ≥ n/2, you can treat the problem as unlimited transactions. The optimal strategy is to iterate through prices and accumulate every positive difference prices[i] - prices[i-1]. This greedy observation avoids the DP entirely and runs in linear time.
Recommended for interviews: Interviewers typically expect the state-compressed dynamic programming solution. It shows you understand transaction state transitions and space optimization. Starting with the state-based DP demonstrates clear reasoning, but reducing it to O(k) space highlights strong DP skills and familiarity with common stock trading patterns.
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.
C++
Java
C#
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.
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.
JavaScript
Time Complexity: O(kn).
Space Complexity: O(kn), uses additional space for the DP table.
| 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). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| State-based Dynamic Programming | O(n * k) | O(n * k) | Best for understanding transaction states and building the DP transitions step by step |
| DP with State Compression | O(n * k) | O(k) | Preferred optimized solution when memory usage matters |
| Greedy (k ≥ n/2) | O(n) | O(1) | When the transaction limit is large and effectively allows unlimited trades |
Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming • Tushar Roy - Coding Made Simple • 178,545 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock IV with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor