6.7 buy and sell a stock twice

#1

I’m confused about how the backward phase in the code works if it’s calculating the maximum profit if we buy on day i, instead of calculating the maximum profit if we buy on OR AFTER day i.
<12,11,13,9,12,8,14,13,15>
For example, if i = 6, the max profit would be whatever profit we calculated from the first subarray + (15-14) = 1, instead of first subarray profit + (15-13)=2.

maxPriceSoFar = Math.max(maxPriceSoFar, prices.get(i));
maxTotalProfit = Math.max(
maxTotalProfit,
maxPriceSoFar - prices.get(i) + firstBuySellProfits.get(i - 1));

Thanks!

0 Likes
#2

This is how I understand it,
The forward phase calculate for the given “time range” (day 0 -> day i) the maximum profit one can get on the first trade (first buy and sell).
The backward phase calculate for the corresponding “time range” (day i to day <prices.size()>-1) the maximum profit one can get on the second trade (second buy and sell).

So if i = 6, the backward phase would calculate the maximum profit of a trade (buy and sell) between day 6-8, which is buy on day 7 and sell on day 8 (skipping day 6 since day 7 is cheaper to buy). In this way we can get more profit on the second “peak”, maximizing the total profit.

This is the whole idea with two computations

0 Likes
#3

Hi @fondant,

The idea is exactly like what @yhzs88 said, and the first phase tries to get the maximum you can get with one buy, and the second backward phrase tries to get the maximum you can get after buying it for the first time.

0 Likes
#4

No wait I’m sorry I’m still confused :frowning:
I understand the first phase (I think), but still having trouble with the backward phase.

So if i = 6, the backward phase would calculate the maximum profit of a trade (buy and sell) between day 6-8, which is buy on day 7 and sell on day 8 (skipping day 6 since day 7 is cheaper to buy).

The code doesn’t seem to skip day 6. Rather, the code forces you to purchase on day 6 (i).
maxPriceSoFar - prices.get(i) + firstBuySellProfits.get(i - 1)
The maxprice would be 15, but prices.get(i) would be 14.

0 Likes
#5

so when i = 6, we get
maxTotalProfit = Math.max(
maxTotalProfit,
1 + firstBuySellProfits.get(i - 1));

instead of

maxTotalProfit = Math.max(
maxTotalProfit,
2 + firstBuySellProfits.get(i - 1));

0 Likes
#6

This code is optimized (to calculated the final combined profit at once) so it may be confused.

For the sake of clarity I would rather make it exact symmetric as the first phase (then as a third step calculate the combined profit) but lets analyze this optimized code:

Since there is a Math.max() surrounding this computation anyways, the previous round (for day i=7, remember we are going backwards in this phase) wins since the “firstBuySellProfits” can only be equal and bigger for larger i. So we are indirectly taking the largest profit between day 6-8 by doing this Math.max() so the previous value from i=7 wins.

0 Likes
#7

Ah that makes sense! My brain didn’t connect with the fact that the first phase array is always decreasing backwards. Thank you so much!

0 Likes
#8

Hi @fondant,

It would be easier for you to run the code in our solutions page to see what is going. Also shout out to @yhzs88 for providing the explanation as well.

0 Likes
#9

I didn’t understand in the backward phase why you skip the first index.
for i, price in reversed(list(enumerate(prices[1:],1)))
You mentioned F[-1] = 0. And question says, atmost 2 buys. So there can be 1 right?

0 Likes