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 9^th day, then we would consider that selling on the 9^th 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 9^th day will give us the maximum profit. For instance, the price of the stock on the 9^th day is 80 units. Now, if we see the lowest price before 9^th day was at 6^th day which was 20 units. So, if we would have bought the stock on the 6^th day for 20 and sell at the price of 80 on the 9^th 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 6^th 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:

1. What is the max profit of this day when selling on this day is compulsory?
2. 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

Why?

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.

1. 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.
2. 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.
3. 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.