Best Time to Buy and Sell Stock IV
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring every possible sequence of transactions. It uses a recursive function that, for each day, decides between the possible actions: buy, sell, or do nothing. This generates a decision tree of all possibilities, and the path with the maximum profit is chosen.
Algorithm
- Define a recursive function
solve(index, k, isHolding). - Base Case: If
index >= prices.lengthor we cannot make any more transactions, return 0. - If
isHoldingis true (we have a stock):- Calculate profit from selling today:
prices[index] + solve(index + 1, k - 1, false). - Calculate profit from holding:
solve(index + 1, k, true). - Return the maximum of these two options.
- Calculate profit from selling today:
- If
isHoldingis false (we don't have a stock):- Calculate profit from buying today:
-prices[index] + solve(index + 1, k, true). - Calculate profit from skipping today:
solve(index + 1, k, false). - Return the maximum of these two options.
- Calculate profit from buying today:
- The initial call to the function would be
solve(0, k, false).
Walkthrough
The core of this method is a recursive function, let's call it solve(day, transactions_completed, holding). This function calculates the maximum profit achievable from a given day onwards, given that we have already completed transactions_completed and our holding status (whether we own a stock or not).
- State: The state is defined by
(day, transactions_completed, holding). - Transitions:
- If we are
holdinga stock, we can either sell it today (which incrementstransactions_completed) or hold it and move to the next day. - If we are not
holdinga stock, we can either buy one today (which changes ourholdingstatus) or skip today and move on.
- If we are
- Base Cases: The recursion stops when we have exhausted the days (
day >= prices.length) or completed the maximum allowed transactions (transactions_completed >= k). In these scenarios, no further profit can be made, so we return 0.
The final answer is the result of the initial call solve(0, 0, false).
class Solution { public int maxProfit(int k, int[] prices) { return solve(0, 0, 0, k, prices); } private int solve(int day, int transactions, int holding, int k, int[] prices) { // Base case: no more days to trade or max transactions reached if (day >= prices.length || transactions >= k) { return 0; } // Recursive step // Option 1: Do nothing today (rest) int restProfit = solve(day + 1, transactions, holding, k, prices); int actionProfit; if (holding == 1) { // Option 2: Sell the stock actionProfit = prices[day] + solve(day + 1, transactions + 1, 0, k, prices); } else { // holding == 0 // Option 3: Buy the stock actionProfit = -prices[day] + solve(day + 1, transactions, 1, k, prices); } return Math.max(restProfit, actionProfit); }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Conceptually straightforward and follows the problem statement directly.
Cons
Extremely inefficient due to exponential time complexity.
Results in 'Time Limit Exceeded' for even moderately sized inputs.
Redundantly computes the same subproblems multiple times.
This approach enhances the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We store the result for each state (day, transactions, holding) in a cache (a 3D array). When the recursive function is called for a state that has been solved before, we simply return the cached result, pruning the recursion tree significantly. This is a top-down dynamic programming approach.
Algorithm
- Create a 3D memoization table
memo[n][k+1][2]and initialize it with a value indicating 'not computed' (e.g., -1). - Use the same recursive function
solve(day, transactions, holding)as in the brute-force approach. - Before any computation, check if
memo[day][transactions][holding]has already been computed. If so, return the stored value. - If not, perform the recursive calculations as before.
- After computing the result for a state, store it in
memo[day][transactions][holding]before returning it. - The initial call remains
solve(0, 0, 0, k, prices, memo).
Walkthrough
We keep the same recursive structure but add a 3D array, memo[n][k+1][2], to store the results of subproblems. memo[day][transactions][holding] will store the maximum profit for the state defined by the indices.
Before computing the profit for a state, we first check our memo table. If a valid result (i.e., not our initial placeholder value) exists, we return it immediately. Otherwise, we compute the result using the same recursive logic as the brute-force method, and crucially, we store this new result in the memo table before returning. This ensures that each unique subproblem is solved only once.
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n == 0) return 0; int[][][] memo = new int[n][k + 1][2]; for (int[][] dayMemo : memo) { for (int[] transMemo : dayMemo) { Arrays.fill(transMemo, -1); } } return solve(0, 0, 0, k, prices, memo); } private int solve(int day, int transactions, int holding, int k, int[] prices, int[][][] memo) { if (day >= prices.length || transactions >= k) { return 0; } if (memo[day][transactions][holding] != -1) { return memo[day][transactions][holding]; } int restProfit = solve(day + 1, transactions, holding, k, prices, memo); int actionProfit; if (holding == 1) { actionProfit = prices[day] + solve(day + 1, transactions + 1, 0, k, prices, memo); } else { // holding == 0 actionProfit = -prices[day] + solve(day + 1, transactions, 1, k, prices, memo); } memo[day][transactions][holding] = Math.max(restProfit, actionProfit); return memo[day][transactions][holding]; }}Complexity
Time
O(n * k)
Space
O(n * k)
Trade-offs
Pros
Guaranteed to find the optimal solution.
Drastically more efficient than brute-force, making it feasible for the given constraints.
Maintains the intuitive recursive structure.
Cons
Requires O(n * k) space for the memoization table, which can be large.
May lead to a stack overflow for very deep recursion, although the problem constraints make this unlikely.
This is the most efficient approach, utilizing bottom-up dynamic programming with space optimization. We observe that the calculation for the current day i only depends on the results from the previous day i-1. This allows us to reduce the space complexity from O(n*k) to O(k). We maintain two arrays, buy and sell, of size k+1, representing the maximum profit at each transaction count, ending in a 'holding' or 'not holding' state, respectively.
Algorithm
- Handle edge cases: if
n <= 1ork == 0, return 0. - Apply an optimization: if
k >= n / 2, the problem is equivalent to unlimited transactions. Solve it in O(n) time by summing all positive price differencesprices[i] - prices[i-1]and return. - Create two arrays,
sell[k+1]andbuy[k+1]. - Initialize
sellwith all 0s andbuywithInteger.MIN_VALUE. - Iterate through each
pricein thepricesarray. - Inside this loop, iterate
jfrom 1 tok. - Update the
buyandsellarrays based on the transitions:buy[j] = max(buy[j], sell[j-1] - price)sell[j] = max(sell[j], buy[j] + price)
- After iterating through all prices, the answer is
sell[k].
Walkthrough
Instead of a large 2D or 3D DP table, we only need to keep track of the profits for the previous day to calculate the profits for the current day. We can achieve this with two 1D arrays:
sell[j]: The maximum profit after completingjtransactions, ending in a state where we are not holding any stock.buy[j]: The maximum profit afterjbuys, ending in a state where we are holding a stock.
We iterate through each day's price and update these two arrays. For each price and for each transaction count j from 1 to k, we apply the following transitions:
- To update
buy[j], we consider either holding the stock we bought previously (buy[j]) or buying a stock today. If we buy today, our profit is the profit fromj-1completed transactions (sell[j-1]) minus the current price.buy[j] = max(buy[j], sell[j-1] - price) - To update
sell[j], we consider either doing nothing (sell[j]) or selling the stock we are holding today. If we sell, our profit is the profit from holding the stock for thej-th transaction (buy[j]) plus the current price.sell[j] = max(sell[j], buy[j] + price)
An important optimization is to check if k >= n / 2. If it is, we can perform as many transactions as we want. The problem then simplifies to 'Best Time to Buy and Sell Stock II', which can be solved in O(n) time.
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n <= 1 || k == 0) { return 0; } // Optimization: if k is large enough, it's the same as unlimited transactions. if (k >= n / 2) { int maxProfit = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; } int[] sell = new int[k + 1]; int[] buy = new int[k + 1]; Arrays.fill(buy, Integer.MIN_VALUE); for (int price : prices) { for (int j = 1; j <= k; j++) { buy[j] = Math.max(buy[j], sell[j - 1] - price); sell[j] = Math.max(sell[j], buy[j] + price); } } return sell[k]; }}Complexity
Time
O(n * k)
Space
O(k)
Trade-offs
Pros
Optimal time complexity of O(n * k).
Optimal space complexity of O(k).
Iterative approach avoids recursion overhead and potential stack overflow issues.
Cons
The logic can be less intuitive to derive compared to the recursive top-down approach.
Solutions
Solution
public class Solution { public int MaxProfit(int k, int[] prices) { int n = prices.Length; int[, ] f = new int[k + 1, 2]; for (int j = 1; j <= k; ++j) { f[j, 1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j > 0; --j) { f[j, 0] = Math.Max(f[j, 1] + prices[i], f[j, 0]); f[j, 1] = Math.Max(f[j - 1, 0] - prices[i], f[j, 1]); } } return f[k, 0]; }}class Solution {public int maxProfit(int k, int[] prices) { int n = prices.length; int[][] f = new int[k + 1][2]; for (int j = 1; j <= k; ++j) { f[j][1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j > 0; --j) { f[j][0] = Math.max(f[j][1] + prices[i], f[j][0]); f[j][1] = Math.max(f[j - 1][0] - prices[i], f[j][1]); } } return f[k][0]; }}class Solution {public: int maxProfit(int k, vector<int> &prices) { int n = prices.size(); int f[k + 1][2]; memset(f, 0, sizeof(f)); for (int j = 1; j <= k; ++j) { f[j][1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j; --j) { f[j][0] = max(f[j][1] + prices[i], f[j][0]); f[j][1] = max(f[j - 1][0] - prices[i], f[j][1]); } } return f[k][0]; }};class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) if n < 2: return 0 # 3-D dp: n days * k completed transactions * 2 ops buy/sell # my understanding, one transaction, meaning both buy then sell completed dp = [[[ 0 ] * 2 for _ in range ( k + 1 )] for _ in range ( n )] for i in range ( 1 , k + 1 ): dp [ 0 ][ i ][ 1 ] = - prices [ 0 ] # dp[][][ 0/1 ], 1 is buy, 0 is sell for i in range ( 1 , n ): for j in range ( 1 , k + 1 ): dp [ i ][ j ][ 0 ] = max ( dp [ i - 1 ][ j ][ 1 ] + prices [ i ], dp [ i - 1 ][ j ][ 0 ]) # [1] => sell happening <= that day dp [ i ][ j ][ 1 ] = max ( dp [ i - 1 ][ j - 1 ][ 0 ] - prices [ i ], dp [ i - 1 ][ j ][ 1 ]) return dp [ - 1 ][ k ][ 0 ] ############## class Solution : def maxProfit ( self , k : int , prices : List [ int ]) -> int : @ cache def dfs ( i , j , k ): if i >= len ( prices ): return 0 ans = dfs ( i + 1 , j , k ) if k : ans = max ( ans , prices [ i ] + dfs ( i + 1 , j , 0 )) elif j : ans = max ( ans , - prices [ i ] + dfs ( i + 1 , j - 1 , 1 )) return ans return dfs ( 0 , k , 0 ) ############## import heapq import random class Solution ( object ): def findKthLargest ( self , nums , k ): """ :type A: List[int] :type k: int :rtype: int """ def quickselect ( start , end , nums , k ): if start == end : return nums [ start ] mid = partition ( start , end , nums ) if mid == k : return nums [ mid ] elif k > mid : return quickselect ( mid + 1 , end , nums , k ) else : return quickselect ( start , mid - 1 , nums , k ) def partition ( start , end , nums ): p = random . randrange ( start , end + 1 ) pv = nums [ p ] nums [ end ], nums [ p ] = nums [ p ], nums [ end ] mid = start for i in range ( start , end ): if nums [ i ] >= pv : nums [ i ], nums [ mid ] = nums [ mid ], nums [ i ] mid += 1 nums [ mid ], nums [ end ] = nums [ end ], nums [ mid ] return mid return quickselect ( 0 , len ( nums ) - 1 , nums , k - 1 ) def maxProfit ( self , k , prices ): """ :type k: int :type prices: List[int] :rtype: int """ if not prices : return 0 stack = [] heap = [] v = p = 0 n = len ( prices ) ans = 0 while p < n : v = p while v < n - 1 and prices [ v ] >= prices [ v + 1 ]: v += 1 p = v + 1 while p < n and prices [ p ] > prices [ p - 1 ]: p += 1 while stack and prices [ stack [ - 1 ][ 0 ]] > prices [ v ]: _v , _p = stack . pop () heap . append ( prices [ _p - 1 ] - prices [ _v ]) while stack and prices [ stack [ - 1 ][ 1 ] - 1 ] < prices [ p - 1 ]: heap . append ( prices [ stack [ - 1 ][ 1 ] - 1 ] - prices [ v ]) v , _ = stack . pop () stack . append (( v , p )) heap += [ prices [ p - 1 ] - prices [ v ] for v , p in stack ] if len ( heap ) < k : return sum ( heap ) self . findKthLargest ( heap , k ) return sum ( heap [: k ])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.