Simple JAVA Solution


  • 0

    We have 3 variables:
    Sell(i): the optimal solution when stock is sold on day i
    Buy(i): the optimal solution when stock is hold/bought on day i
    Rest(i): the optimal solution when stock was sold in advance, and we do nothing on day i (i.e. cool down)

    Then we can come up with following equations:

    1. The optimal solution of sell the stock on day(i) is:
      Sell(i) = Buy(i-1) + prices[i];
    2. The optimal solution of buy the stock on day(i) is:
      Buy(i) = max(Buy(i-1), Rest(i-1) - prices[i]);
    3. The optimal solution of cool-down on day(i) is:
      Rest(i) = max(Rest(i-1), Sell(i-1))

    Then we can come up with the following piece of code:
    ...

    public int maxProfit(int[] prices) {
        int prevSell = 0, prevRest = 0, prevBuy = Integer.MIN_VALUE;
        for(int i = 0; i < prices.length; i++) {
            int newBuy = Math.max(prevBuy, prevRest-prices[i]);
    
            prevRest = Math.max(prevSell, prevRest);
            prevSell = prevBuy+prices[i];
            prevBuy = newBuy;
        }
        
        return Math.max(prevRest, prevSell);
    }
    

    ...


Log in to reply
 

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