Best Time to Buy and Sell Stock III

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.

Basically, we have to buy the stock at the minimum possible price and sell at the maximum possible price, keeping in mind that we have to sell the stock before buying it again.

Below is the detailed algorithm: 

1. Call a recursive function ‘maxProfitHelper’ by passing four parameters i.e., 'prices’, starting index, number of transactions, and a boolean variable ‘IsBought’. ‘IsBought’ will help us engage in just one transaction at a time. Initially, ‘IsBought’ is false.

maxProfitHelper(‘prices’, ‘index’, ‘trans’, ‘isBought’): 

1. Base Condition: When we are out of days, or the transactions left are 0, return 0 as you can not do anything.
2. Now we have three options:
   • If ‘isBought’ is false:
     • Buy the stock: Recursively find the profit made by the remaining items by setting ‘isBought’ as true and ‘index’ as ‘index’ + 1. Note that buying a stock is a loss of ‘prices[index]’.
   • If ‘isBought’ is true:
     • Sell the stock: Recursively find the profit made by the remaining items by decreasing the transactions by 1 and ‘index’ as ‘index’ + 1. Note that selling a stock is a profit of ‘prices[index]’.
   • Skip the day, Recursively find the profit made by the remaining items by setting ‘index’ as ‘index’ + 1.
3. Return the maximum profit obtained by any of the above options.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems repeatedly. 
 

Below is the detailed algorithm: 

The idea is to use memoization.

1. Create a 3-D lookup table of size (2 *  3  * ('n')), where ‘n’ is the number of days. The lookup table stores the solutions to the subproblems where ‘lookup[isBought][tran][index]’ denotes the maximum profit you can earn by doing at most ‘tran’ transactions in first 'index' days.
2. Initialize the table by -1.
3. Now, we will call a recursive function ‘maxProfitHelper’ by passing five parameters i.e., ‘prices’, starting index, number of transactions, and a boolean variable ‘isBought’, and the ‘lookup’ table. ‘isBought’ will help us in engaging in just one transaction at a time. Initially, ‘isBought’ is false.
    

maxProfitHelper('prices', ‘index', ‘tran’, ‘isBought’, ‘lookup’):

1. Base Condition: When we are out of days, or the transactions left are 0, return 0 as you can not do anything.
2. If the current subproblem has been solved already, return the value stored in the ‘lookup’ table.
3. Now we have three options:
   • If ‘isBought’ is false:
     • Buy the stock: Recursively find the profit made by the remaining items by setting ‘isBought’ as true and 'index' as 'index' + 1. Note that buying a stock is a loss of ‘prices[index]’.
   • If ‘isBought’ is true:
     • Sell the stock: Recursively find the profit made by the remaining items by decreasing the transactions by 1 and 'index' as 'index' + 1. Note that selling a stock is a profit of 'prices[index]’.
   • Skip the day, Recursively find the profit made by the remaining items by setting 'index' as 'index' + 1.
4. Store the maximum profit obtained by any of the above options into the 'lookup’ table and finally return it.

• The idea is to create a 2-D array ‘maxProfit’ of size (3) * (n).
• Initially, all the elements of the ‘maxProfit’ matrix will be 0.
• Now, the value ‘maxProfit[i][j]’ denotes the maximum profit we can earn by doing 'i' transactions up to ‘j-th’ day.

The detailed algorithm to fill the ‘maxProfit’ matrix is as follows:

1. L1 : Run a loop from ‘k’ = 1 to 2 to consider the both transactions:
   • Select the ‘minValue’ as 'prices[0]'.
   • L2: Run a loop from ‘i’ = 1 to ‘n’ to consider the prices of each day:
     For the ‘kth’ transaction,
     • If we don’t trade on the ‘i-th’ day, then the profit will be the same as the ‘i-1th’ day.
     • If we buy the stock on ‘j-th’ day [ j < i ] and sell on the ‘i-th’ day, then the profit is (‘prices[i]’ - ‘prices[j]’) + ‘maxProfit[k - 1][j - 1]’.
     • Thus, update:
       ‘minValue’ = min(‘minValue’ , ‘prices[i]’ - ‘maxProfit[k - 1][i - 1]')
       'maxProfit[k][i]’ = max( ‘maxProfit[k][i - 1]' , ‘prices[i]’ - ‘minValue’). 
       Also, note that L1 and L2 will be two nested loops.
2. Return ‘maxProfit[2][N - 1]’, the final profit that can be earned.

We observe that the approach for the question goes in the following way:

First buy → First sell →  Second buy →  Second sell

Now, as, at the end we need maximum profit, let us think of it like this. Suppose you currently have Rs. 100 with you. You buy a stock of some amount, say ‘X’. The amount left with you is 100 - ‘X’. Now, if you sell the stock at an amount, say ‘ Y ‘, you are left with a total amount of 100 - ‘X’ + ‘Y’. 

During the second transaction, you buy a stock of price ‘A’ and sell it at price ‘B’. The total amount becomes 100 - ‘X’ + ‘Y’ - ‘A’ + ‘B’. Now, all you need to do is maximize the money that you have. 
 

Below is the detailed algorithm:

1. Initialize variables 'firstBuy' as the minimum negative value, ‘firstSell’ as 0, ’secondBuy’ as the minimum negative value, and 'secondSell’ as 0.
   ‘firstSell’ will be the profit after the first transaction, and 'secondSell’ will be the profit after the second transaction.
2. For ‘i’ in range days:
   • Maximise 'firstBuy' as max( 'firstBuy', - ‘prices[i]’), this is the amount left after your first buy.
   • Maximise 'firstSell' as max( 'firstSell' , 'firstBuy' + 'prices[i]’).
   • Maximise 'secondBuy' as max( 'secondBuy', 'firstBuy' - ‘prices[i]’).
   • Maximise 'secondSell' as max( 'secondSell' , 'secondBuy' + ‘prices[i]’).
3. Return 'secondSell' as it is the final profit or the final amount left with you.