In this case, the net profit earned from the current transaction will be + Arr. Option 2: The other option is to sell the stock on the current day.And the ‘cap’ variable will remain the same as if no transaction took place.
As we have not bought the stock, the ‘buy’ variable value will still remain at 1, indicating that we can’t buy and only sell the stock the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1,1, cap). Option 1: To do no transaction and move to the next day.As we have only bought the stock and not sold it the transaction remains incomplete and the ‘cap’ variable value remains unchanged.Ĭase 2: When buy = 1, we can sell the stock. As we have bought the stock, the ‘buy’ variable value will change to 1, indicating that we can’t buy and only sell the stock the next day. To calculate the maximum profit starting from the next day, we will recursively call f(ind+1,1, cap). As we are buying the stock, we are giving money out of our pocket, therefore the profit we earn is negative. In this case, the net profit earned from the current transaction will be -Arr. Option 2: The other option is to buy the stock on the current day.As we have not bought the stock, the ‘buy’ variable value will still remain 0, indicating that we can buy the stock the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1,0, cap). If we can buy the stock on a particular day, we have two options: We will use the pick/non-pick technique as discussed in this video “ Recursion on Subsequences”.Ĭase 1: When buy = 0, we can buy the stock. To do nothing and move on to the next day.To either buy/sell the stock(based on the buy variable’s value and if ‘cap’ > 0).Step 2: Try out all possible choices at a given index. We need to always keep in mind this constraint. Next, we have a cap on the number of transactions that we can make. Therefore we need a second variable ‘buy’ which tells us on a particular day whether we can buy or sell the stock. Next, we need to respect the condition that we can’t buy a stock again, that is we need to first sell a stock, and then we can buy that again. We need to think in the terms of the number of days, therefore one variable will be the array index( say ind). Step 1: Express the problem in terms of indexes. We will first form the recursive solution by the three points mentioned in the Dynamic Programming Introduction. As we need to try out all the possible choices, we will use recursion. Therefore we need to generate all the choices in order to compare the profit. Solution :Įvery day, we will have two choices, either to do nothing and move to the next day or to buy/sell (based on the last transaction and the number of transactions left) and find out the profit. But we can’t sell before buying and can’t buy before selling any previously bought stock.ĭisclaimer: Don’t jump directly to the solution, try it out yourself first. In other words, we first buy a stock and then sell it. We can’t buy a stock again after buying it once.In order to sell the stock, we need to first buy it on the same or any previous day.We can buy and sell the stock any number of times.The following guidelines need to be followed: It represents the price of a stock on ‘n’ days. Problem Link: Best Time to Buy and Sell Stock III
0 kommentar(er)
