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


  • 79
    E

    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;
    	int has0_Buy = -prices[0];
    	for(int i=1; i<L; i++) {
    		has1_doNothing = has1_doNothing > has0_Buy ? has1_doNothing : has0_Buy;
    		has0_Buy = -prices[i] + has0_doNothing;
    		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;
    }
    

    Please leave your comment if any question.

    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


  • 1
    C

    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?


  • 0
    E

    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.


  • 0
    E

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


  • 0
    C

    I know now, thank you.


  • 0
    E

    Glad to hear that!


  • 0
    C

    Very straight forward explanation.


  • 0

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


  • 0
    J

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


  • 0
    S

    ”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.


  • 0
    C

    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?


  • 0
    C

    @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.
    

  • 1
    Z

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


  • 2
    L

    @ElementNotFoundException said in Very Easy to Understand One Pass O(n) Solution with No Extra Space:

    has1_doNothing = has1_doNothing > has0_Buy ? has1_doNothing : has0_Buy;
    has0_Buy = -prices[i] + has0_doNothing;
    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?


  • 0
    B

    @ElementNotFoundException
    has0_doNothing is cooldown condition ?


  • 0
    Y

    This is a solution I can understand. Thank you.


  • 0
    U

    @coryang1991 I have the same question...


Log in to reply
 

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