1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

During the forward pass, you compute F such that F[i] represents the maximum possible profit when restricting yourself to the elements with indices 0,1..,i.

During the backward pass, you compute B such that B[i] represents the maximum possible profit when restricting yourself to the elements with indices i,i+1,..,n-1 (where n is the size of your list). The reason you track the max is that because you are going backwards in time when populating B, you want to sell before you buy.

Now M[i] = F[i-1] + B[i] represents the maximum profit when doing a first buy/sell among indices 0,1..,i-1 and a second buy/sell among indices i,i+1..,n-1, so you are sure that the first sell will happen before the second buy (because the first sell happens at index i-1 at the latest and the second buy at index i at the earliest).

Reciprocally, suppose the optimal solution has two buy/sell's happening at indices b1, s1, b2, s2 (in increasing order). Then you know that M[b2] will be at least as big as the profit achieved by this solution (equal in fact, because it can't be bigger) as b1,s1 happens before index b2, and b2,s2 happens after (or at) b2.

Thus, by taking the maximum over all M[i] you will necessarily hit M[b2] at some point and get the maximum profit. And if the optimal solution has only one buy/sell it will be at M[0] = F[n-1] = B[0] = M[n-1] which you also consider.

$\endgroup$
  • $\begingroup$ Could you clarify why we go backwards in time in the second loop and not simply do another forward pass with different boundaries ($i, n - 1$)? Also, why does the backward pass loop over the whole range instead of $i, n - 1$ in the solution code? How does tracking the max correlate to going backwards through the data? $\endgroup$ – Anton Zabirko Aug 25 at 22:21
  • $\begingroup$ How would you achieve this with a forward pass? When reaching $i$ during a forward pass, you have no information on all the indices that come after $i$, so i don't see how you would compute the best profit for elements in $(i,n-1)$. That's why a backward pass is useful, when reaching $i$ you already know the best selling point in $(i+1,n-1)$ so you know how much profit you could make by buying at $i$ (and selling at the maximum in $(i+1,n-1)$). $\endgroup$ – Tassle Aug 25 at 22:28
  • $\begingroup$ Can't you change the $i$ to equal $n - 1$ and get a new maximum; effectively doing the same algorithm on both halves of the array? Could you also explain why the maximum is tracked? That's the last piece of the puzzle for me, as your post helped with a lot of it. $\endgroup$ – Anton Zabirko Aug 25 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.