The link to the problem: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.
Constraints: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
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.Thoughts:
This problem is the transformation of 121. Best Time to Buy and Sell Stock and 122. Best Time to Buy and Sell Stock II. I explain the idea of how we solve these problems here.
However, this problem is much harder than the previous two. It is possible that one transaction is better than 2 transactions; it is also possible that the two highest transactions are conflicted, etc. Hence, we cannot just find the two highest profits individually and adding them together as the return value.
Code Logic:
The idea I’m going to introduce now doesn’t perform the best performance among others. (Because I need to use extra spaces to make the idea understandable) But I guarantee this will be the easiest solution to understand among others. It just based on the idea of how we can solve the problem 121 and 122.
We use two arrays left, right to store max profit on that day. That is to say, we will see if it is worth selling on the day i when we traverse from left to right; we will also see if it is worth buying on the day i when we traverse from right to left.
⚠️ Instead of using day 1 as our first day, in this article, I will assume day 0 is our first day. It is easier to explain since all the arrays we have are zero based.
Before we go into the code and the example, there are several variables in the code and I would like to introduce them first —
- left: an array that stores the max profit from day 0 to the day i
- right: an array that stores the max profit from the last day to the day i
- minPrice: the minimum price we have met till the day i (i.e., the best buying price)
- maxPrice: the maximum price we have met from the last day to the day i (i.e., the best selling price)
- maxProfit: always holding the maximum profit we can get when we reach day i
Let’s take the above example when prices = [3,3,5,0,0,3,1,4] for example.
🚧 Let’s show how we update our “left array” - the goal is to find the best day to sell!
🔧Step 0. minPrice is the price on day 0. We assume day 0 is the best day to buy the stock.
🔧Step 1. On Day 0 and Day 1, the profit will be 0 since the minimum buying price we have met so far is 3, which is the same price if we want to sell.
🔧Step 2. On Day 2, we decide to sell since we can get a higher profit (original profit is 0). Hence the highest profit now is $2.
🔧Step 3. On Day 3, we decide not to do any action since we cannot get the profit that is higher than we had yesterday. Hence, the highest profit we can get is the same as yesterday.
We also met a lower price to buy, so we can update minPrice and make Day 3 a best buying day.
🔧Step 4. On Day 4, we decide not to do any action. Hence, the highest profit we can get is the same as yesterday.
🔧Step 5. On Day 5, we decide to sell! Since we found that if we sell today, we can earn the highest profit.
🔧Step 6. On Day 6, we decide not to do any action. Hence, the highest profit we can get is the same as yesterday.
🔧Step 7. On Day 7, we decide to sell! Since we found that if we sell today, we can earn the highest profit.
Done! So now we know the highest profit we can get from day 0 to each day if we are only allowed to do one transaction.
🚧 Let’s show how we update our “right array” — the goal is to find the best day to buy!
🔧Step 0. maxPrice is the price on day 7. We assume day 7 is the best day to s sell he stock.
🔧Step 1. On Day 7, the profit will be 0 since if we buy today, we won’t earn any money.
🔧Step 2. On Day 6, we decide to buy the stock! Since if we buy, we can earn the highest profit $3 so far.
🔧Step 3. On Day 5, we decide not to do any action. Hence, the highest profit we can get is the same as “tomorrow”. (i.e., since we know the future, we decide don’t buy it till day 6)
🔧Step 4. On Day 4, we decide to buy the stock! Since if we buy, we can earn the highest profit $4 so far.
🔧Step 5. On Day 3, we decide not to do any action. Hence, the highest profit we can get is the same as “tomorrow”.
🔧Step 6. On Day 2, we decide not to do any action. Hence, the highest profit we can get is the same as “tomorrow”.
We also met a higher price to sell, so we can update maxPrice and make Day 2 the best selling day.
🔧Step 7. On Day 1 and Day 0, we decide not to do any action since we cannot reach the highest profit. Hence, the highest profit we can get is the same as Day 2.
Done! So now we know the highest profit we can get from day 7 to each day if we are only allowed to do one transaction.
The last step is to add left[i] and right[i] together and find the maximum profit since we can actually do 2 transactions.
Below is the 7ms code that beats 30%:
public int maxProfit(int[] prices) {
int n = prices.length;
int[] left = new int[n];
int[] right = new int[n];
int minPrice = prices[0];
int maxProfit = 0;
for(int i=1;i<n;i++)
{
int profit = prices[i]-minPrice;
if(profit<0)
minPrice = prices[i];
else if(profit > maxProfit)
maxProfit = profit;
left[i] = maxProfit;
}
int maxPrice = prices[n-1];//maximum price we can sell
maxProfit = 0;
for(int i=n-2;i>=0;i--)
{
int profit = maxPrice - prices[i];
if(profit<0)
maxPrice = prices[i];
else if(profit > maxProfit)
maxProfit = profit;
right[i] = maxProfit;
}
maxProfit = 0;
for(int i=0;i<n;i++)
maxProfit = Math.max(maxProfit,left[i]+right[i]);
return maxProfit;
}The time complexity of the above code is O(3n).
We can also improve it to O(2n) by merging the 3rd loop into the 2nd loop like the below 2ms code that beats 99% :
public int maxProfit(int[] prices) {
int n = prices.length;
int[] left = new int[n];
int[] right = new int[n];
int minPrice = prices[0];
int maxProfit = 0;
for(int i=1;i<n;i++)
{
maxProfit = Math.max(maxProfit,prices[i]-minPrice);
if(minPrice>prices[i])
minPrice = prices[i];
left[i] = maxProfit;
}
int maxPrice = prices[n-1];
maxProfit = 0;
int totalMAX = 0;
for(int i=n-1;i>=0;i--)
{
maxProfit = Math.max(maxProfit,maxPrice-prices[i]);
if(maxPrice<prices[i])
maxPrice = prices[i];
right[i] = maxProfit;
totalMAX = Math.max(totalMAX,left[i]+right[i]);
} return totalMAX;
}
