My explanation for O(N) solution!


  • 90
    H

    First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).

    sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i ] + buy1, we want to make this max.

    buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max

    sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.

    So sell2 is the most money we can have.

    Hope it is helpful and welcome quesions!

    public int maxProfit(int[] prices) {
    		int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
    		for (int i = 0; i < prices.length; i++) {
    			buy1 = Math.max(buy1, -prices[i]);
    			sell1 = Math.max(sell1, buy1 + prices[i]);
    			buy2 = Math.max(buy2, sell1 - prices[i]);
    			sell2 = Math.max(sell2, buy2 + prices[i]);
    		}
    		return sell2;
    	}

  • 2
    M

    hi han35,
    it is a great solution! this seems very logical financially, but math-wise it is very hard to explain. Can you provide some details for the calculation?


  • 7

    @mxue This is already math explaination. The transition relation is constructed by the following four equations. Actually, sell2 is the only state we record for iterations. The others are intermediate states.

    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, buy1 + prices[i]);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, buy2 + prices[i]);
    

    If you still do not understand, see below.

    buy1 and *sell1 *are for the first transaction. buy2 and *sell2 *are for the second transaction.

    Transition relation:

    1. buy1[i] = max( - prices[i], buy1[i - 1])
    2. sell1[i] = max(buy1[i - 1] + price[i], sell1[i - 1])
    3. buy2[i] = max( sell1[i -1] - prices[i], buy2[i - 1])
    4. sell2[i] = max(buy2[i - 1] + price[i], sell2[i - 1])

  • 0
    This post is deleted!

  • 2
    R

    In fact , It is more reasonable to do update as order : sell2, buy2, sell1, buy1.

    Because for update every value at the current time , we should use previous state ! using sell2, buy2, sell1, buy1 satisfied .

    But the result it still ok for your code. I can't know the reason directly, may be it is really ok.


  • 2
    X

    @han35

    The Transition Relation implied in this code is:

    buy1[i] = max(-prices[i], buy1 Last Changed)
    sell1[i] = max(buy1 Last Changed + price[i], sell1 Last Changed)
    buy2[i] = max(sell1 Last Changed - prices[i], buy2 Last Changed)
    sell2[i] = max(buy2 Last Changed + price[i], sell2 Last Changed)

    instead of:

    buy1[i] = max(-prices[i], buy1[i - 1])
    sell1[i] = max(buy1[i - 1] + price[i], sell1[i - 1])
    buy2[i] = max(sell1[i -1] - prices[i], buy2[i - 1])
    sell2[i] = max(buy2[i - 1] + price[i], sell2[i - 1])

    For example,
    If buy1 changed on day i, in your code, update sell1 on day i means cancel buy1 on day i.
    However, for transition sell1[i] = max(buy1[i - 1] + price[i], sell1[i - 1]), it means buy on a day before day i and sell it on day i.

    @readonlyfile
    I had the same concern with you!
    There must be some hidden logics hard to understand that make sure this code is right.


  • 0
    M

    If you do 1st sell at day i, how do you avoid doing the 2nd buy at the same day? Thx!


  • 5
    R

    To understand the hidden logic, you have to understand what these 4 variables stand for.

    sell2: Final profit.
    buy2: Best profit so far, if you buy the stock not after Day i (2nd transaction).
    sell1: Best profit so far, if you sell the stock not after Day i (1st transaction).
    buy1: Minimum price to buy the stock.

    The logic between buy1 and sell1 is quite straight forward. What you need to do is simply find a minimum price to buy and sell it some days after.
    Of course, sell1 won't update if the profit is not greater than before even if you buy the stock at a lower price. Let's assume you sell the stock at Day a to get the greatest profit for the 1st transaction, which stores in sell1.

    Now comes the trick. Assume you find a better deal at Day b, sell1 get updated. So you have 2 choice for buy2:

    • not update buy2, you still sell your stock at Day a. Nothing changed.
    • update buy2 with new sell1, which means you sell the stock at Day b.
      buy2 = sell1 - price[i] means you sell you stock at Day b and buy it at Day i. And Day i is definitely not early than Day b, which is the hidden logic.

  • 0
    L

    @han35 said in My explanation for O(N) solution!:

    First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).

    sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i ] + buy1, we want to make this max.

    buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max

    sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.

    So sell2 is the most money we can have.

    Hope it is helpful and welcome quesions!

    public int maxProfit(int[] prices) {
    		int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
    		for (int i = 0; i < prices.length; i++) {
    			buy1 = Math.max(buy1, -prices[i]);
    			sell1 = Math.max(sell1, buy1 + prices[i]);
    			buy2 = Math.max(buy2, sell1 - prices[i]);
    			sell2 = Math.max(sell2, buy2 + prices[i]);
    		}
    		return sell2;
    	}
    

    why test case int[] s = {3,3,5,0,0,3,1,4}; return 6 but not 8


  • 0
    S

    so clear and thank you very much :)


  • 0

    Use the other type of for loop:

        public int maxProfit(int[] prices) {
           int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE, sell1 = 0, sell2 = 0;
           for(int price: prices){
             buy1 = Math.max(buy1, -price);
             sell1 = Math.max(sell1, price + buy1);
             buy2 = Math.max(buy2, sell1 - price);
             sell2 = Math.max(sell2, price + buy2);
           }
           
           return sell2;
        }

  • 0
    Y

    Hi @han35 , it seems that according to your explanation "buy2 means we want to buy another stock, we already have sell1 money", we can only buy the 2nd stock after selling the first one?

    And could anyone explain if we want to store the intermediate state, what do we use? Like a [n][4] matrix?

    Thanks a lot!


  • 0
    X
    This post is deleted!

  • 2
    C

    @readonlyfile I think you are right!
    But the reason why this version of code is really ok is because:
    Buy action at day i doesn't make any change to sell action at day i. We are all focus on code, so we can't jump out of the puzzle.We should focus on the scenario more.
    We take the key code for example:

            buy1[i] = Math.max(buy1[i-1], -prices[i]);
            sell1[i] = Math.max(sell1[i-1], buy1[i] + prices[i]);
            buy2[i] = Math.max(buy2[i-1], sell1[i] - prices[i]);
    	sell2 = Math.max(sell2[i-1], buy2[i] + prices[i]);
    

    if buy1 updated at day i,it means we buy one stock.We note this as:
    buy1[i] = max(-prices[i], buy1[i - 1])
    Then sell1 will not be updated,although buy1 has been updated.Please think the scenario :
    if sell1 updated at the same day i,it means we did nothing at this day(we buy one and we sell one,the result will be stay with sell1[i-1]).
    So buy1 and sell1 will not changed at the same day.
    sell1[i] = Math.max(sell1[i-1], buy1[i] + prices[i]);
    sell1[i] will stay with sell[i-1] or changed with prices[i].The buy action at this time will make no change to sell.

    The same reason with sell1 and buy2,buy2 and sell2.

    At day i we can just make one action,we buy it or we sell it.If we sell it and buy it,we just make an useless tranction.We must save tranction to make more money.So the order of buy1,sell1,buy2,sell2 is okay.

    But I think your logic is rigorous,the right order should be sell2, buy2 ,sell1, buy1。


  • 0
    K

    @han35
    Very good and simple explanation.
    How should we make this simple to extend for 'N' transactions?


Log in to reply
 

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