Welcome back, dear reader. Hope you are doing well. So, today we are going to discuss the next problem in our stock problems series and this problem is Buy and Sell Stocks- Two Transactions Allowed. We recommend you to watch the Buy and Sell Stocks- Two Transactions Allowed before moving on with this question as this problem will require your previous knowledge as a strong prerequisite.
Buy and Sell Stocks- Two Transactions Allowed
The stock market is filled with individuals who know the price of everything but the value of nothing.
~ Philip Fishcher
So, let's move to this problem. We have been given n numbers representing n number of days and we are given n numbers representing the price of a stock in those n days. We have to find the maximum profit that we can obtain when only two transactions are allowed. Also, there cannot be any overlapping transaction meaning you have to sell a purchased stock before buying another one. We recommend you to refer to the BUY AND SELL STOCK-TWO TRANSACTIONS ALLOWED video (0:00-0:53) to understand the question completely. So, dear reader, we recommend you to try and solve this problem yourself first and then come again to the article to understand the concepts in-depth and gain some extra knowledge.
We will study the question by placing the stock prices on a graph and analyzing the what, how, and why of the question. So, let us take an example of the stock prices of a stock for 19 days. The stock prices are as shown below:
These are the stock prices of a stock for 19 days. We will analyze the question with the help of this graphical representation. Let us first recall what we did for the same question, when only one transaction was allowed.
Buying and Selling Stocks- One Transaction Allowed (Recapitulation)
Dear reader, we request you to first check out the question BUYING AND SELLING STOCKS-ONE TRANSACTION ALLOWED and also watch its solution video so that you already get a good hold of the concept we are going to talk about and understand the concepts in depth.
So, if you recall, we used to find out the maximum profit for each day by considering that the selling on that particular day is mandatory. For instance, if we want to know the maximum profit that can be earned on the 9th day, then we would consider that selling on the 9th day is mandatory. After that, we will find out the lowest price of the stock before that day so, buying on that day and selling on the 9th day will give us the maximum profit. For instance, the price of the stock on the 9th day is 80 units. Now, if we see the lowest price before 9th day was at 6th day which was 20 units. So, if we would have bought the stock on the 6th day for 20 and sell at the price of 80 on the 9th day, we will get the maximum profit of day 9 i.e. 80-20=60. You may refer to the solution video to understand the above procedure completely. So, we are storing the maximum profit for a particular day, assuming it is essential to sell the stocks on that day. So, if we apply this procedure for each day, we will find the maximum profit as shown in the diagram below:
The number written in blue denotes the maximum profit for each day which is calculated by subtracting the lowest price of the stock before that day from the selling price of the current day. The profits of those days are zero which have the lowest price till their day.
Now, let us come back to our question and see what we are going to do this time.
Maximum Profit Till This Day.
Earlier, we were calculating the maximum profit that we could make by selling the stock if it was mandatory to sell on the same day. Now, it is again mandatory to sell the stock every day, but, we will now not store/calculate the maximum profit for that day, rather we will calculate the maximum profit till that day. Look at the diagram shown below:
Let us start from day 1. Here, we have a stock price of 30. So, if we consider this day as both buying and selling day, the max profit for this day is 0. Also, we do not have any day before this, So, the maximum profit till this day is 0.
Let us consider day 2. For buying at a lower price it is essential to buy on a day when the price is lower. So, we buy on day 1 and we sell on the current day. So, the max profit for that day is 10. Now, the maximum profit till that day is also 10 as the profit before it was zero and 10 is greater than 0. This is the profit of buying on day 1 and selling on day 2. This is shown in the figure by writing b1s2 with the profit.
Now, we are on day 3. The max profit for day 3 is the price of the stock at day3 - the price of the stock at day1 ( which is the lowest price till day 3) i.e. 43-30=13. Also, this is the max profit till day3 which was made by selling on day3 and buying on day1 indicated by b1s3.
Similarly, the maximum profit of day 4 is the maximum profit so far indicated by b1s4 (profit=20). Now, we will calculate the maximum profit for day 5. The maximum profit for day 5 is the price of the stock at day 5 minus the price of the stock at day 1 =45-30=15. Now, the max profit till date is not 15. Rather, it is 20 which was a result of the transaction b1s4 i.e. buying on day1 and selling on day4. So, we will now not store 15, rather we will store 20 as the max profit till day 5. Hey, wait for a second! Where are we storing these profits? Apply your knowledge of Dynamic Programming, we will talk about this in a later section of this article.
Similarly, we keep on moving until we get the next lowest cost of the stocks. Then, from that day onwards, that day will become the buying day for every transaction, but this day doesn't need to be the buying day in the max profit till day transaction. For instance, in the diagram given below, on the 6th day we got the lowest price, so this is the buying day from here but still, the maximum profit was 20 which was due to transaction b1s4.
You may refer to the solution video to understand the above part completely if you have any doubts about it.
Maximum Profit at this Day (Buying is Mandatory):
Till now, we have discussed two points:
- What is the max profit of this day when selling on this day is compulsory?
- What is the max profit till this day if selling on this day is compulsory?
If you notice in both these processes, we moved in a forward direction i.e. from day 1 to day 19. Now, we will move from day 19 to day 1 and obtain the maximum profit of this day when buying on this day is compulsory. See, earlier we were purchasing/ buying stocks on a particular day when the price was minimum and selling them on a particular day gave us max profit for that day. Now, we will buy at a date and sell when the price is maximum.
The difference between these two methods is that in the first method the profit is based on buying at the lowest price and in the second method the profit is based on selling at the highest price.
Look at the diagram given below and watch the solution video to understand the below diagram and the above-explained part completely.
We started from day 19. It is mandatory to purchase stocks here. Since we purchased stocks here and further there is no value greater than 55 (as there is no value further) the max profit here is 0.
Now we are at day 18. Here, we have purchased the stocks at a cost of 50. We see that in the future, on day19, the price of stocks is 55 which is greater than the buying price. So, selling on day 19 will give us the max profit on day 18. So, the transaction is b18s19, and the max profit=55-50=5.
Now, we are at day17. Here, the buying cost is 17. In the future, there is no day with a price greater than 70. So, the stocks bought on day17 should be sold the same day to avoid loss. So, the max profit will be 70-70=0 and the transaction is b17s17. Similarly, we move forward and analyze the max profit for every day.
Maximum Profit From This Day (Buying is Mandatory)
Now, we will discuss what can be the maximum profit from a particular day onwards that can be obtained. The focus is to buy the stock (which is mandatory) on that particular day and sell it at the max price. Dear reader, we request you to watch the solution video to understand the diagram below completely :
We started from day19 and the max profit was 0 for that day(you already know this).
Now, we are at day 18. Here we can see from the fig-5 that the max profit for this day is 5 i.e. 55-5=5. Now, we want the maximum from this day onwards. Since 5 is greater than 0, the maximum profit from this day onwards is 5 and the transaction is b18s19. Then, we move to day 17. There is no value greater than day 70, so we will buy and sell this stock on day 17 only and the max profit for this day is 0. But, we have a max profit for day 18 which is greater than this profit. So, the max profit from day 17 onwards is 5.
And the transaction remains the same i.e. b18s19. Similarly, we can fill in this data for each day.
Finding Max Profit:
Now, we will combine fig-6 and fig-4. The transactions of fig-4 are denoted with brown color and the transactions of fig-6 are denoted with green color.
Now, if you think carefully we have two non-overlapping transactions each day. One where stocks are bought and sold before or on the same day and the other in which the stocks are bought and sold after that day. The sum of these two maximum profits at each day will give us the max profit that can be obtained by making two transactions
This is because there are two non-overlapping transactions each giving a maximum profit. Dear reader, we request you to watch the solution video to understand the why of the problem carefully
Now that we know the What and Why of the problem let's move to its how.
- Storage and Capacity: We will need two arrays, one that will store the max profit till the current day and the other that will store the maximum profit from the current day onwards. Each element of the first array will mean the max profit that can be made till that day and each element of the second array will signify the max profit that can be made from that day onwards.
- The direction of solving: The first array will be solved from 0 to n i.e. we will traverse in a forward direction as the smaller problem i.e storing the max profit till day1 is on the left and storing the max profit till day n is the larger problem and it is on the right. Whereas on the other hand, we will traverse the second array in a backward direction as storing max profit from day n onwards is a small problem and storing max profit from day 1 onwards is a large problem.
- Traverse and solve: While traversing both the arrays we will fill in the required values and then we will find the max value from the sum of these two arrays and that will be the maximum profit.
Now that we know the what, why, and how of the question and have understood the entire procedure let us move on to the code.
- Storage and Meaning: Make two arrays of size n+1 and store the max profits till day and max profit from the day onwards in each of them respectively. Each element in the first array means the max profit till that day and each element in the second element represents the max profit from that day onwards.
- The direction of Solving: The first array will be solved in a forward direction i.e. from 0 to n and the second array will be solved from n to 0.
- Traverse and Solve: Traverse each array and fill the values in them. Then take the sum of these values and the maximum value will be our answer.
So, dear reader, if you have any doubts regarding the above code, you may watch the solution video to clear all your doubts. Now, let us analyze the time and space complexity.
The time complexity of the above code is O(n) as we are traversing the arrays of length n, where n is the number of days.
As we have created two arrays of size n+1, the space complexity of the above method is O(n).
So, dear reader, we hope that you understood the problem and also got the code. If you still have any doubts regarding anything you may refer to the complete solution video for clearing all your doubts.
Here are some suggestions from our side that you don't want to miss:
- This was a really hard problem, we agree. But, every hard problem can be made simple and that's what our team is trying to do for you. So, we suggest you watch the solution video once, completely. You will understand each and every step in depth after that.
- This is an entire series of stock buying and selling problems. You are suggested to revise each problem once again because after this we are moving to the last problem of the series as well as dynamic programming in Foundation. Till then, Happy Coding!!