Share my thinking process


  • 703

    The series of problems are typical dp. The key for dp is to find the variables to represent the states and deduce the transition function.

    Of course one may come up with a O(1) space solution directly, but I think it is better to be generous when you think and be greedy when you implement.

    The natural states for this problem is the 3 possible transactions : buy, sell, rest. Here rest means no transaction on that day (aka cooldown).

    Then the transaction sequences can end with any of these three states.

    For each of them we make an array, buy[n], sell[n] and rest[n].

    buy[i] means before day i what is the maxProfit for any sequence end with buy.

    sell[i] means before day i what is the maxProfit for any sequence end with sell.

    rest[i] means before day i what is the maxProfit for any sequence end with rest.

    Then we want to deduce the transition functions for buy sell and rest. By definition we have:

    buy[i]  = max(rest[i-1]-price, buy[i-1]) 
    sell[i] = max(buy[i-1]+price, sell[i-1])
    rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
    

    Where price is the price of day i. All of these are very straightforward. They simply represents :

    (1) We have to `rest` before we `buy` and 
    (2) we have to `buy` before we `sell`
    

    One tricky point is how do you make sure you sell before you buy, since from the equations it seems that [buy, rest, buy] is entirely possible.

    Well, the answer lies within the fact that buy[i] <= rest[i] which means rest[i] = max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is never occurred.

    A further observation is that and rest[i] <= sell[i] is also true therefore

    rest[i] = sell[i-1]
    

    Substitute this in to buy[i] we now have 2 functions instead of 3:

    buy[i] = max(sell[i-2]-price, buy[i-1])
    sell[i] = max(buy[i-1]+price, sell[i-1])
    

    This is better than 3, but

    we can do even better

    Since states of day i relies only on i-1 and i-2 we can reduce the O(n) space to O(1). And here we are at our final solution:

    Java

    public int maxProfit(int[] prices) {
        int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
        for (int price : prices) {
            prev_buy = buy;
            buy = Math.max(prev_sell - price, prev_buy);
            prev_sell = sell;
            sell = Math.max(prev_buy + price, prev_sell);
        }
        return sell;
    }
    

    C++

    int maxProfit(vector<int> &prices) {
        int buy(INT_MIN), sell(0), prev_sell(0), prev_buy;
        for (int price : prices) {
            prev_buy = buy;
            buy = max(prev_sell - price, buy);
            prev_sell = sell;
            sell = max(prev_buy + price, sell);
        }
        return sell;
    }
    

    For this problem it is ok to use INT_MIN as initial value, but in general we would like to avoid this. We can do the same as the following python:

    Python

    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        sell, buy, prev_sell, prev_buy = 0, -prices[0], 0, 0
        for price in prices:
            prev_buy = buy
            buy = max(prev_sell - price, prev_buy)
            prev_sell = sell
            sell = max(prev_buy + price, prev_sell)
        return sell

  • 1
    M

    That's the clearest answer so far. Thank you!


  • 76

    Based on how you approach this problem, I will hire you before the end of the interview!


  • 17

    Ok. Let's talk about the signing bonus then ^_^.


  • 3
    N

    Great thinking process!

    How did u come up with the state as
    "any sequence end with sell/buy/rest before i"?

    After the previous buy and sell problems, all I can think is something like
    "any sequence end with operation, and this operation happens at i".


  • 11

    I kind of think if someone throws me this question in a phone screen, he intends to see me fail.


  • 0

    Because this problem says "as many transactions as you want", unlike only one or two transactions.


  • 0

    unless you practiced this already ^_^.


  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 11
    W

    sorry i don't get this line.

    buy[i]  = max(rest[i-1]-price, buy[i-1]) 
    

    shouldn't it only can be "rest" before "buy"?
    and the same in sell[i] and rest[i].


  • 0
    S

    you can own a stock for multiple days, i.e. you don't have to sell it in the next day.


  • 1
    X

    What a clear thinking process. If I could think like this before solving, I don't worry about solve a problem. Good post. Helpful.


  • 0

    I don't quite understand your question. Can you give me an example of what you are referring?


  • 0
    N

    Thank you so much!


  • 0
    D

    The hint on this question says "Binary Tree". Can you explain why that was mentioned?


  • 2
    W

    buy[i] = max(rest[i-1]-price, buy[i-1])

    sell[i] = max(buy[i-1]+price, sell[i-1])

    rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

    i am refering this.

    in the first line ,buy[i] = max(rest[i-1]-price, buy[i-1]) ,i can uderstand rest[i]-price,but i don't understand buy[i-1]. i wonder why it compare to buy[i-1]


  • 0
    W
    This post is deleted!

  • 24

    I am Chinese. I see. You need to understand the definition of them.

    buy[i] compare to buy[i-1] is because the definition of buy[i] is the maxProfit of ALL sequences end with buy BEFORE i.

    For example

    prices = [1,5,3,4]

    buy[0] = -1 max of [buy]

    buy[1] = -1 max of [buy], [rest, buy]

    buy[2] = -1 max of [buy], [rest, buy], [rest, rest, buy]

    buy[3] = 0 max of [buy], [rest, buy], [rest, rest, buy], [rest, rest, rest, buy], [buy, sell, rest, buy]

    Do you see my point?


  • 7

    Also this line buy[i] = max(rest[i-1]-price, buy[i-1]) doesn't means it will result in [buy, buy].

    If i wrote buy[i] = max(rest[i-1]-price, buy[i-1]-price) then it means what you think it means.

    when buy[i] = buy[i-1] it actually just skip buying on day i because the profit is not optimal.


Log in to reply
 

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