Explanation for algorithm + why this is DP
There are several solutions that invoke some recursive formula resembling\n\nProfit_if_sold[i] = max(0, Profit_if_sold[i-1] + Diff_from_last[i])\n\nwithout moti
There are several solutions that invoke some recursive formula resembling\n```\nProfit_if_sold[i] = max(0, Profit_if_sold[i-1] + Diff_from_last[i])\n```\nwithout motivating how this formula is obtained. This post provides the explanation for **how** one arrives at this recursive formula.\n\n1. To arrive at this formula, you must first identify the optimal strategy. Realize that at time ```i```, you have three possible actions: buy, hold, or sell. The optimal actions to take are:\n\ta. **Buy the stock** if it is the minimum price-to-date, i.e. ```P_i < P_j``` for all ```j < i```\n\tb. **Hold / sell the stock** if it is not at the minimum price to-date, i.e. ```P_j < P_i``` for some ```j < i```\n\n2. To implement the strategy, it is informative to look at a concrete example:\n```\nPrices =         [7, 1, 5, 3, 6, 4, 0, 7] \nMin_to_date =    [7, 1, 1, 1, 1, 1, 0, 0] \nProfit_if_sold = [0, 0, 4, 2, 5, 3, 0, 7]\nDiff_from_last = [0,-6, 4,-2, 3,-2,-4, 7]\n```\n* ```Prices``` are the stock prices\n* ```Min_to_date``` is the minimum price to date\n* ```Profit_if_sold``` is the profit if a stock was sold at step ```i```; note that it is ```0``` if is the min-to-date, as that would be the time to buy according to the strategy\n* ```Diff_from_last[i] = P[i] - P[i-1]```\n\nIt is clear that the solution to the problem statement is ```max(Profit_if_sold)```. So how do you calculate ```Profit_if_sold```? You calculate it using the recursive formula\n```\nProfit_if_sold[i] = max(0, Profit_if_sold[i-1] + Diff_from_last[i]) \n```\nThis is the recursive formula used in several solutions. As this a recursive formula, one can consider this problem a DP problem
[]