Going through the EPI book and I need some help understanding this part.
There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The input is given as a list of ints. The example they give is:
[12, 11, 13, 9, 12, 8, 14, 13, 15]
So here the maximum profit from a single buy-sell event is 7; buy at 8 and sell at 15. From two buy-sell events it is 10; buy at 9, sell at 12 and buy at 8, sell at 15.
The intuition for a single buy-sell is simple where we just keep track of the minimum element in the list and the difference between the minimum and the current element is the profit.
What I don't understand is how the double buy-sell formula works. The book proposes a solution where two passes are made through the data, a forward and a backward pass. The forward pass uses the same formula as above (single buy-sell), but the backward pass starts at the back of the list and keeps track of the maximum instead. The profits of the backward pass are stored in an array and added to the profits of the forward pass with $M[i] = F[i - 1] + B[i]$, and where $F[-1] = 0$.
Why does the backward pass keep track of the maximum, and how does the formula ensure that we won't buy before the second sale?
Here is the solution code given:
def buy_and_sell_stock_twice(prices: List[float]) -> float: max_total_profit, min_price_so_far = 0.0, float('inf') first_buy_sell_profits = [0.0] * len(prices) for i, price in enumerate(prices): min_price_so_far = min(min_price_so_far, price) max_total_profit = max(max_total_profit, price - min_price_so_far) first_buy_sell_profits[i] = max_total_profit # Now for the backwards pass. max_price_so_far = float('-inf') for i, price in reversed(list(enumerate(prices[1:], 1))): max_price_so_far = max(max_price_so_far, price) max_total_profit = max( max_total_profit, max_price_so_far - price + first_buy_sell_profits[i - 1]) return max_total_profit
I broke down the iterator in the reverse pass and it creates:
[(8, 15), (7, 13), (6, 14), (5, 8), (4, 12), (3, 9), (2, 13), (1, 11)]
The expected backwards pass result is also provided for the sample data:
B = [7, 7, 7, 7, 7, 7, 2, 2, 0]
Looking through the code I can see how the algorithm can be used to populate B. What doesn't make sense is why this backwards pass guarantees the max profit, how it guarantees sane buys and sells, and what the intuition is for doing it this way.
I looked at similar questions but they provide different solutions which work great but don't provide any insight on the book's solution. The book is also not readily available online so there is less content on the material.