I am going through the book Elements of Programming Interview and have gotten stuck at the solution to the "Buy and Sell A Stock Twice" problem.
Write a program that computes the maximum profit that can be made by buying and selling a share at most twice. The second buy must be made on another date after the first sale.
The solution is explained by the authors below:
Suppose we record the best solution for A[0, j], j between 1 and n-1, inclusive. Now we can do a reverse iteration, computing the best solution for a single buy-and-sell for A[j, n-1], j between 1 and n-1, inclusive. For each day, we combine this result with the result from the forward iteration for the previous day- this yields the maximum profit if we buy and sell once before the current day and once at or after the current day. For example, suppose the input array is [12, 11, 13, 9, 12, 8, 14, 13, 15]. Then the most profit that can be made with a single buy and sell by Day i (inclusive) is F = [0, 0, 2, 2, 3, 3, 6, 6, 7]. Working backwards the most profit that can be made with a single buy and sell on or after Day i is B = [7,7,7,7,7,7,2,2,0]. To combine these two, we compute m[i] - F[i - 1] + B[i], where F[-1] is taken to be 0 (since the second buy must happen strictly after the first sell. This yields M = [7, 7, 7, 9, 9, 10, 5, 8, 6].
My Questions Are:
How is the algorithm working on a higher level. I do not understand why we are doing a reverse iteration at all. I understand the forward iteration, it simply gives you the most profit if you buy and sell 1 time.
Where is the equation M[i] = F[i - 1] + B[i] come from?
how are they obtaining B = [7, 7, 7, 7, 7, 7, 2, 2, 0]? I tried to do the reverse iteration and arrive at entirely different values
By saying "between 1 and n - 1" inclusive, do they mean 1 and n-1 are included?