Watch 10 video solutions for Best Time to Buy and Sell Stock V, a medium level problem involving Array, Dynamic Programming. This walkthrough by codestorywithMIK has 7,616 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 stock in dollars on the ith day, and an integer k.
You are allowed to make at most k transactions, where each transaction can be either of the following:
Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].
Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.
Return the maximum total profit you can earn by making at most k transactions.
Example 1:
Input: prices = [1,7,9,8,2], k = 2
Output: 14
Explanation:
We can make $14 of profit through 2 transactions:Example 2:
Input: prices = [12,16,19,19,8,1,19,13,9], k = 3
Output: 36
Explanation:
We can make $36 of profit through 3 transactions:
Constraints:
2 <= prices.length <= 1031 <= prices[i] <= 1091 <= k <= prices.length / 2Problem Overview: You are given an array where prices[i] is the stock price on day i. The goal is to maximize profit by buying and selling the stock multiple times with a limit on the number of transactions. Each transaction consists of one buy followed by one sell, and you cannot hold multiple stocks at the same time.
Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)
The naive approach explores every possible action on each day: buy, sell, or skip. Recursively simulate decisions while tracking whether you currently hold a stock and how many transactions remain. For every day, branch into multiple possibilities and compute the resulting profit. This approach demonstrates the full decision tree but quickly becomes impractical because the number of states grows exponentially. It mainly helps build intuition for the dynamic programming transition.
Approach 2: Dynamic Programming with Transaction States (O(n * k) time, O(n * k) space)
Dynamic programming removes repeated work by storing results for each state. Define dp[i][t][h] where i is the day, t is the number of completed transactions, and h indicates whether you are holding a stock. Transition by either skipping the day, buying, or selling. Buying moves from h = 0 to h = 1 while keeping the transaction count the same. Selling moves from h = 1 to h = 0 and increments the transaction count. Iterating through days and transactions fills the DP table and guarantees the optimal profit. This approach is the standard pattern used in many dynamic programming stock problems.
Approach 3: Space Optimized Dynamic Programming (O(n * k) time, O(k) space)
The full DP table is unnecessary because each state depends only on the previous day. Instead of storing results for every day, keep two arrays: one for buy states and one for sell states for each transaction count. Iterate through the price array and update the arrays in place using transitions such as buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price). This reduces memory usage significantly while preserving the same time complexity. The technique appears frequently in array optimization problems and advanced DP interview questions.
Recommended for interviews: Start by explaining the recursive decision process (buy, sell, skip). Then move to the DP formulation with transaction states. Interviewers usually expect the O(n * k) dynamic programming solution and often appreciate the space‑optimized version since it demonstrates deeper understanding of DP state transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual understanding of all possible buy/sell decisions |
| Dynamic Programming with 3D State | O(n * k) | O(n * k) | General solution when transaction count is limited |
| Space Optimized DP | O(n * k) | O(k) | Large inputs where memory usage matters |