Share my Java accepted DP solution.


  • 0
    Z
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length < 2) return 0;
            int[] dp = new int[prices.length]; // dp[i] means the maxProfit for day i;
            
            // init for day 0 and day 1
            dp[0] = 0;
            dp[1] = Math.max(0, prices[1] - prices[0]);
            
            //After day 0 and 1, prevBuyMax records the max amount from previous days when day i you can do the sell
            int prevBuyMax = Math.max(-prices[0], -prices[1]);
            
            for (int i = 2; i < prices.length; i++) {
                // dp[i] is the max of: cooldown on day i (dp[i - 1]), or do the sell on day i (prevBuyMax + prices[i])
                dp[i] = Math.max(dp[i - 1], prevBuyMax + prices[i]);
                
                // Update prevBuyMax for day i, you have two choices:
                // buy before day i (prevBuyMax, from last day),
                // or cooldown on day i - 1 and buy on day i (dp[i - 2] - prices[i])
                prevBuyMax = Math.max(prevBuyMax, dp[i - 2] - prices[i]);
            }
            
            return dp[prices.length - 1];
        }
    

Log in to reply
 

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