Need help with Algorithm Design question from Kleinberg Problem 6.7! Any help wi
ID: 3551253 • Letter: N
Question
Need help with Algorithm Design question from Kleinberg Problem 6.7! Any help will be appreciated!
We wish to study the price of a given stock over n consecutive days, numbered i = 1,2,... ,n. For each day p(i) is the price per share for the stock on that day. (Assume that the price of a share does not change during each day.) How should we choose a day i on which to buy the stock and a later day j > i on which to sell it, if we want to maximize the profit per share, i.e., p(j) - p(t)? If there is no way to make money during the n days, we should calculate the profit to be zero. Describe a dynamic programming algorithm to find the optimal numbers i and j in O(n) time. Please provide a proof of correctness and running time of your algorithm.Explanation / Answer
The trick is to start from the end. Stock trade is easy if time goes backwards!
If you think code is easier to read than words, just skip my explanation, but here goes:
Reading from the end, look at price of that day. Is this the highest price so far (from the end), then sell! The last day (where we start reading) you will always sell.
Then go to the next day (remember, backwards in time). Is it the highest price so far (from all we looked at yet)? - Then sell all, you will not find a better day. Else the prices increase, so buy. continue the same way until the beginning.
The whole problem is solved with one single reverse loop: calculating both the decisions and the profit of the trade.
Here's the code in C-like python