# Very Easy to Understand One Pass O(n) Solution with No Extra Space

• The idea is as follows:

First, think about what we can do on day `i`? You either have one stock or you don't on day `i`. For each case, you have two options, making a total of four possible actions on day `i`:

1. you have 1 stock and you sell it
2. you have 1 stock and you do nothing
3. you have 0 stock and you buy stock `i`
4. you have 0 stock and you do nothing

As you can imagine, these four actions are correlated between day `i-1` and day `i`. For example, if you take action 1 on day `i`, you then have either taken action 2 or 3 on day `i-1` but not 1 or 4. In precise, two consecutive days are related as follows:

1. if you take action 1 on day `i` ==> you have either taken action 2 or 3 on day `i-1`
2. if you take action 2 on day `i` ==> you have either taken action 2 or 3 on day `i-1`
3. if you take action 3 on day `i` ==> you must have taken action 4 on day `i-1` (you can not sell on day `i-1` due to cool down)
4. if you take action 4 on day `i` ==> you have either taken action 1 or 4 on day `i-1`

Now you want to maximize your total profit, but you don't know what action to take on day `i` such that you get the total maximum profit, so `you try all 4 actions on every day`. Suppose you take action 1 on day `i`, since there are two possible actions on day `i-1`, namely actions 2 and 3, you would definitely choose the one that makes your profit on day `i` more. Same thing for actions 2 and 4. So we now have an iterative algorithm.

Before coding, one detail to emphasize is that the initial value on day `0` is important. You basically cannot take action 1, so the corresponding profits should be 0. You cannot take action 2 in practice, but you cannot set up the profit to 0, because that means you don't have a stock to sell on day `1`. Therefore, the initial profit should be negative value of the first stock. You can also think of it as you buy the stock on day `-1` and do nothing on day `0`.

Here comes the code in Java:

``````public int maxProfit(int[] prices) {
int L = prices.length;
if(L < 2) return 0;

int has1_doNothing = -prices[0];
int has1_Sell = 0;
int has0_doNothing = 0;
for(int i=1; i<L; i++) {
has0_doNothing = has0_doNothing > has1_Sell ? has0_doNothing : has1_Sell;
has1_Sell = prices[i] + has1_doNothing;
}
return has1_Sell > has0_doNothing ? has1_Sell : has0_doNothing;
}
``````

If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java

• I have two questions.

1. "if you take action 3 on day i ==> you can only take the same action on day i-1 (you can not sell on day i-1 due to cool down)
if you take action 4 on day i ==> you have either taken action 1 or 3 on day i-1
". Is there some mistakes?

2.In the code.
" has1_Sell = prices[i] + has1_doNothing;"// here has1_doNothing has been changed before, don't we buffer it before change?

• For the first one, could you explain where exactly you see a mistake?

For the second one, no, it is not a mistake. If you take a closer look at the four actions, you will realize that we actually do need to updated has1_doNothing to update has1Sell. You can try buffering it with a new variable and you will see why so.

• I see a mistake now in my explanation. See updated text. Thanks for pointing out.

• I know now, thank you.

• Very straight forward explanation.

• I got confused by everyone else's explanation until I see this. Totally a life saver, thank you tons！！Upvoted for sure

• It is very clear and the code is so nice!
thanks for sharing.

• ”You cannot take action 2 in practice, but you cannot set up the profit to 0, because that means you don't have a stock to sell on day 1.“

The sentence structure "cannot, but cannot" makes me confuse.

Can you rephrase it a little bit? Thanks.

• Hi can i check with you why we do need to consider case 2 might happen on day i-1 while case 2 happens on day i in the following line?
has1_Sell = prices[i] + has1_doNothing;

I think we only considered that if we hold the stock on day i-1 here. It's also possible that we bought the stock on day i right?

• @steven10 I think the following explanation would be helpful.

``````the initial value on day 0 is important.
-->You basically cannot take action 1, so the corresponding profits (has1_Sell) should be 0.
-->You can take action 2 in practice, You can think of it as you bought the stock on day -1 and do nothing on day 0. Since you spent money buying a stock, the initial profit (has1_doNothing) should be negative value of the first stock.
-->You can take action 3. Again, your profit (has0_Buy) will be negative of the first stock.
-->You cannot take action 4. If you do that you don't have anything to sell on day 1. So, profit (has0_doNothing) in this case is 0.
``````

• Just dropping by to say "thanks" to your explanation of the DP solution :)
By sharing thoughts, we help each other.

• ``````has1_doNothing = has1_doNothing > has0_Buy ? has1_doNothing : has0_Buy;
has0_doNothing = has0_doNothing > has1_Sell ? has0_doNothing : has1_Sell;
has1_Sell = prices[i] + has1_doNothing;
``````

How to determine the order of these four lines?

I mean, why we calculate `has1_doNothing` first, then `has0_Buy`, then `has0_doNothing`, and finally, `has1_Sell`?

• @ElementNotFoundException
has0_doNothing is cooldown condition ?

• This is a solution I can understand. Thank you.

• @coryang1991 I have the same question...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.