Share my 3ms Java DP solution


  • 1
    J
        public int maxProfit(int[] prices) {
        if(prices.length == 0 || prices.length == 1) return 0;
        int[] maxProfit = new int[prices.length];
        maxProfit[0]=0;
        maxProfit[1]=Math.max(0, prices[1]-prices[0]);
        int value = Math.max(0-prices[0],0-prices[1]);
        for(int i = 2; i<prices.length; i++) {
        	int temp = prices[i]+value;
        	if(temp <= maxProfit[i-1]) maxProfit[i] = maxProfit[i-1];
            else maxProfit[i] = temp;
        	
        	if(maxProfit[i-2]-prices[i]>value) value = maxProfit[i-2]-prices[i];
        }
        return maxProfit[prices.length-1];
    }

  • 5
    L

    Awesome!

    I change a little bit for your reference.

    public int maxProfit(int[] p) {
        if(p.length == 0 || p.length == 1) return 0;
        
        int n = p.length;
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = Math.max(0, p[1] - p[0]);
        int buy = Math.max(0 - p[0], 0 - p[1]);
        for(int i = 2; i < n; i++) {
        	dp[i] = Math.max(dp[i - 1], p[i] + buy);
        	
        	buy = Math.max(buy, dp[i - 2] - p[i]);
        }
        return dp[n - 1];
    }
    

  • 0
    Y

    Nice. I didn't realize "value" in original post actually meant the largest profit when we bought at ith day until I saw the name of your variables. Thanks!


  • 0

    Could you please provide some more explanation? About the calculation of 'buy' for the first time and each dp[i] ?


  • 0
    L

    Sorry, just saw your post. The variable buy means, if I buy the stock at this time the highest profit I could make. Initially, the buy should be the bigger one in 0 - p[0], 0 - p[1]. And during the iteration, the buy equals the most profit I could make if I buy the stock at this time or not. If I buy the stock at i, the buy should be dp[i - 2] - p[i], because the dp[i - 2] means the highest profit I can make at time i - 2, and I spent p[i] to buy the stock. So for example, At time i, the dp[i] could be dp[i - 1] means I did nothing, or be p[i] + buy means I bought the stock several days before and sell it at i.


Log in to reply
 

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