Write all codes of dietpepsi's thinking process


  • 1

    @dietpepsi , He writes in https://discuss.leetcode.com/topic/30421/share-my-thinking-process , I think it will be easy to understand if we can see all the codes of his thinking process. Maybe helpful.

    Version 1:

     public int maxProfit(int[] prices) {
            if(prices == null || prices.length <= 1)    return 0;
            int n = prices.length;
            //Solution 1
            int[] buy = new int[prices.length];
            int[] sell = new int[prices.length];
            int[]  rest = new int[prices.length];
            buy[0] = -prices[0];
            sell[0] = 0;
            rest[0] = 0;
            for(int i = 1; i < n; i ++) {
                buy[i] = Math.max(rest[i - 1] - prices[i], buy[i - 1]);
                sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
                rest[i] = sell[i - 1];
            }
            return Math.max(sell[n - 1], rest[n - 1]);
        }
    

    Solution 2

     public int maxProfit(int[] prices) {
            if(prices == null || prices.length <= 1)    return 0;
            int n = prices.length;
            //Solution 2
            int[] buy = new int[prices.length];
            int[] sell = new int[prices.length];
            buy[0] = -prices[0];
            buy[1] = Math.max(-prices[0], -prices[1]);
            sell[0] = 0;
            sell[1] = Math.max(sell[0], prices[1] - prices[0]);
            for(int i = 2; i < n; i ++) {
                buy[i] = Math.max(sell[i - 2] - prices[i], buy[i - 1]);
                sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
            }
            return sell[n - 1];
        }
    
    public int maxProfit(int[] prices) {
           if(prices == null || prices.length <= 1)    return 0;
           int n = prices.length;        
           //Solution 3
           int sell = 0;
           int prev_sell = 0;
           int buy = Integer.MIN_VALUE;
           int prev_buy = 0;
           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;
       }
    

Log in to reply
 

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