Best Time to Buy and Sell Stock III
HardPrompt
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is based on the idea that two non-overlapping transactions can be seen as one transaction in the first part of the time period and another transaction in the second part. We can try every possible split point in the prices array. For each split, we calculate the maximum profit from a single transaction in the left subarray and the right subarray and sum them up. The maximum of these sums over all possible splits will be our answer.
Algorithm
- Initialize
max_profit = 0. - Iterate through each day
ifrom0ton-1, considering it as the day the first transaction's period ends and the second one's begins. - For each
i:- Calculate
profit1, the maximum profit from one transaction inprices[0...i]. - Calculate
profit2, the maximum profit from one transaction inprices[i...n-1]. - Update
max_profit = max(max_profit, profit1 + profit2).
- Calculate
- The final
max_profitis the answer. This also covers the case of a single transaction, as one of the profits can be zero.
Walkthrough
We iterate through the prices array from i = 0 to n-1, where n is the number of days. Each index i serves as a potential split point. The first transaction occurs in prices[0...i] and the second in prices[i...n-1]. For each i, we need a helper function to find the maximum profit from a single transaction in a given subarray. This is the classic "Best Time to Buy and Sell Stock I" problem. The helper function, let's call it maxSingleProfit, iterates through a subarray, keeping track of the minimum price seen so far and the maximum profit that can be achieved. The main loop calculates maxSingleProfit(prices[0...i]) + maxSingleProfit(prices[i...n-1]) and updates a global maximum profit. This naturally handles the case of a single transaction as well, since for any split, one of the sub-problems could yield a profit of zero.
class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } int maxTotalProfit = 0; // The loop iterates through all possible split points. // The first transaction is in prices[0...i] // The second transaction is in prices[i...n-1] for (int i = 0; i < n; i++) { int profit1 = maxSingleProfit(prices, 0, i); int profit2 = maxSingleProfit(prices, i, n - 1); maxTotalProfit = Math.max(maxTotalProfit, profit1 + profit2); } return maxTotalProfit; } // Helper to calculate max profit from one transaction in a subarray private int maxSingleProfit(int[] prices, int start, int end) { if (start >= end) { return 0; } int minPrice = prices[start]; int maxProfit = 0; for (int i = start + 1; i <= end; i++) { maxProfit = Math.max(maxProfit, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return maxProfit; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Correctly breaks down the problem into a simpler subproblem.
Cons
Inefficient and will likely result in a "Time Limit Exceeded" error for large inputs due to its quadratic time complexity.
This approach improves upon the brute-force method by avoiding redundant calculations. Instead of re-calculating the maximum profit for subarrays in each step, we pre-compute them. We use two arrays: left[i] stores the maximum profit from a single transaction in prices[0...i], and right[i] stores the maximum profit from a single transaction in prices[i...n-1].
Algorithm
- Create an array
leftof sizen. - Iterate from
i = 1ton-1. Calculateleft[i]as the maximum profit inprices[0...i]. Keep track of the minimum price seen so far. - Create an array
rightof sizen. - Iterate from
i = n-2down to0. Calculateright[i]as the maximum profit inprices[i...n-1]. Keep track of the maximum price seen so far. - Initialize
max_profit = 0. - Iterate from
i = 0ton-1. Updatemax_profit = max(max_profit, left[i] + right[i]). - Return
max_profit.
Walkthrough
The core idea is the same: split the problem into two single-transaction problems. The maximum profit for two transactions is max(left[i] + right[i]) over all possible split points i.
First, we create an array left of size n. We iterate from left to right to populate it. left[i] will hold the maximum profit achievable from one transaction in the subarray prices[0...i]. This is done by keeping track of the minimum price found so far.
left[i] = max(left[i-1], prices[i] - min_price)
Second, we create an array right of size n. We iterate from right to left to populate it. right[i] will hold the maximum profit from one transaction in prices[i...n-1]. This is done by keeping track of the maximum price found so far.
right[i] = max(right[i+1], max_price - prices[i])
Finally, we iterate from i = 0 to n-1 to find the maximum total profit. The profit for a split at day i is left[i] + right[i]. The maximum profit can also be from a single transaction, which is left[n-1]. This value is also considered in our final loop since right[n-1] would be 0.
class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } // left[i] = max profit in prices[0...i] int[] left = new int[n]; int minPrice = prices[0]; for (int i = 1; i < n; i++) { minPrice = Math.min(minPrice, prices[i]); left[i] = Math.max(left[i - 1], prices[i] - minPrice); } // right[i] = max profit in prices[i...n-1] int[] right = new int[n]; int maxPrice = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { maxPrice = Math.max(maxPrice, prices[i]); right[i] = Math.max(right[i + 1], maxPrice - prices[i]); } int maxTotalProfit = 0; for (int i = 0; i < n; i++) { maxTotalProfit = Math.max(maxTotalProfit, left[i] + right[i]); } return maxTotalProfit; }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Much more efficient than the brute-force approach, with linear time complexity.
Cons
Requires additional space proportional to the input size.
This is the most optimal approach. It solves the problem in a single pass using dynamic programming with a constant number of variables. We can think of the process as a sequence of four actions: buy first stock, sell first stock, buy second stock, sell second stock. We maintain four variables to track the maximum profit at each of these four stages.
Algorithm
- Initialize four variables:
buy1 = -infinity,sell1 = 0,buy2 = -infinity,sell2 = 0. buy1represents the max profit after the first buy.sell1represents the max profit after the first sell.buy2represents the max profit after the second buy.sell2represents the max profit after the second sell.- Iterate through each
pricein thepricesarray:- Update
buy1 = max(buy1, -price). - Update
sell1 = max(sell1, buy1 + price). - Update
buy2 = max(buy2, sell1 - price). - Update
sell2 = max(sell2, buy2 + price).
- Update
- After the loop,
sell2contains the maximum profit. Returnsell2.
Walkthrough
We define four variables to represent the maximum profit after each of the four possible state transitions:
buy1: The maximum profit after buying the first stock. This is equivalent to the negative of the minimum cost to acquire a stock.sell1: The maximum profit after selling the first stock.buy2: The maximum profit after buying the second stock. This is the profit from the first sale minus the cost of the second buy.sell2: The maximum profit after selling the second stock. This is our final answer.
We iterate through the prices array once. In each iteration, we update these four variables based on the current price. The key is that the calculation for a state on day i depends on the states from day i-1.
The state transition equations for each price are:
buy1 = max(buy1, -price): We want to buy at the lowest possible price, so we maximize the 'profit' which is negative cost.sell1 = max(sell1, buy1 + price): We want to sell at the highest price relative to our purchase, maximizing the profit.buy2 = max(buy2, sell1 - price): We buy the second stock. The profitsell1is available, so the new 'profit' state issell1 - price.sell2 = max(sell2, buy2 + price): We sell the second stock, adding the current price to the profit statebuy2.
After iterating through all prices, sell2 will hold the maximum profit achievable with at most two transactions. The logic inherently handles 0, 1, or 2 transactions because the initial profit values are 0.
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) { return 0; } int buy1 = Integer.MIN_VALUE; int sell1 = 0; int buy2 = Integer.MIN_VALUE; int sell2 = 0; for (int price : prices) { // The maximum money we have after buying the 1st stock. buy1 = Math.max(buy1, -price); // The maximum money we have after selling the 1st stock. sell1 = Math.max(sell1, buy1 + price); // The maximum money we have after buying the 2nd stock. buy2 = Math.max(buy2, sell1 - price); // The maximum money we have after selling the 2nd stock. sell2 = Math.max(sell2, buy2 + price); } return sell2; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Highly efficient in both time and space.
It's a clean and concise solution.
Cons
The logic can be less intuitive to grasp initially compared to the splitting approach.
Solutions
Solution
public class Solution { public int MaxProfit(int[] prices) { int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0; for (int i = 1; i < prices.Length; ++i) { f1 = Math.Max(f1, -prices[i]); f2 = Math.Max(f2, f1 + prices[i]); f3 = Math.Max(f3, f2 - prices[i]); f4 = Math.Max(f4, f3 + prices[i]); } return f4; }}public class Solution { public int MaxProfit ( int [] prices ) { int f1 = - prices [ 0 ], f2 = 0 , f3 = - prices [ 0 ], f4 = 0 ; for ( int i = 1 ; i < prices . Length ; ++ i ) { f1 = Math . Max ( f1 , - prices [ i ]); f2 = Math . Max ( f2 , f1 + prices [ i ]); f3 = Math . Max ( f3 , f2 - prices [ i ]); f4 = Math . Max ( f4 , f3 + prices [ i ]); } return f4 ; } }class Solution {public: int maxProfit(vector<int> &prices) { int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0; for (int i = 1; i < prices.size(); ++i) { f1 = max(f1, -prices[i]); f2 = max(f2, f1 + prices[i]); f3 = max(f3, f2 - prices[i]); f4 = max(f4, f3 + prices[i]); } return f4; }};''' - `f1` 表示第一次买入股票后的最大利润； - `f2` 表示第一次卖出股票后的最大利润； - `f3` 表示第二次买入股票后的最大利润； - `f4` 表示第二次卖出股票后的最大利润。 ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : # 第一次买入，第一次卖出，第二次买入，第二次卖出 f1 , f2 , f3 , f4 = - prices [ 0 ], 0 , - prices [ 0 ], 0 for price in prices [ 1 :]: f1 = max ( f1 , - price ) f2 = max ( f2 , f1 + price ) f3 = max ( f3 , f2 - price ) f4 = max ( f4 , f3 + price ) return f4 class Solution : def maxProfit ( self , prices : List [ int ]) -> int : if not prices : return 0 # 0 to i, max profit left_max = [ 0 ] * len ( prices ) tmp_min = prices [ 0 ] for i in range ( len ( prices )): tmp_min = min ( tmp_min , prices [ i ]) left_max [ i ] = max ( left_max [ i - 1 ], prices [ i ] - tmp_min ) if i > 0 else 0 # i to end, max profit right_max = [ 0 ] * len ( prices ) tmp_max = prices [ - 1 ] for i in range ( len ( prices ) - 1 , - 1 , - 1 ): tmp_max = max ( tmp_max , prices [ i ]) right_max [ i ] = max ( right_max [ i + 1 ], tmp_max - prices [ i ]) if i < len ( prices ) - 1 else 0 return max ( left_max [ i ] + right_max [ i ] for i in range ( len ( prices ))) ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ buy1 = buy2 = float ( "-inf" ) sell1 = sell2 = 0 for i in range ( len ( prices )): sell1 = max ( prices [ i ] + buy1 , sell1 ) buy1 = max ( buy1 , - prices [ i ]) sell2 = max ( sell2 , prices [ i ] + buy2 ) buy2 = max ( sell1 - prices [ i ], buy2 ) return max ( sell1 , sell2 )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.