What is a potential purchase day?
If on any day we get better profit than the day before for hasStock state , that day would be a potential purchase day. But we will have to keep in mind that even though the current day is giving better profit does not mean that this current day will be the day that would bring the maximum profit for us (think about the concept of local maxima and global maxima). So we will have to keep a variable tempPurchaseDay that would store the day whenever we get better profit for hasStock state. Whether the tempPurchaseDay brings the maximum profit so far or not will be determined while computing profit for current day for noStock state.
What does "has stock" mean?
Let hasStock [i] denote the maximum profit obtainable at the end of day i when we hold a stock.
What does it mean when a stock doesn't sell at the end of the day?
If we see that we did not get a sale day at the end, then that would mean that the stock price never went up after the first day . So we did not get a chance to sell in order to get non-zero non-negative profit.
Dynamic Programming Interview Questions: How to Maximize Stock Profits
Say you have an array for which the ith element is the price of a given stock on day i.
Initial Thoughts
Sometimes, the structure of how we should tabulate is not as clear at first. A way to gain some insight into this is to first ask yourself, “Is it possible to solve this in linear time (i.e., O (n))?” If yes, then you’re in luck, because chances are you’ll just need to work with a simple 1D array.