Simple O(n) time DP using constant space


  • 0
    M
    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices == null || prices.length < 2) return 0;
            int maxBuying = -prices[0];
            prices[0] = 0;
            for(int i = 1; i < prices.length; i++) {
                int currPrice = prices[i];
                prices[i] = Math.max(prices[i-1], prices[i] + maxBuying);
                maxBuying = Math.max(maxBuying, (i-2 >=0?prices[i-2]:0)-currPrice);
            }
            
            return prices[prices.length - 1];
        }
    }
    

Log in to reply
 

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