Watch 10 video solutions for Best Time to Buy and Sell Stock IV, a hard level problem involving Array, Dynamic Programming. This walkthrough by Tushar Roy - Coding Made Simple has 178,545 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |