Java DP solution in O(n) time and O(n) space - With clear explanation in comments


  • 1
    D
    public class Solution 
    {
        public int maxProfit(int[] prices) 
        {
            if(prices.length <= 1) return 0;
            
            if(prices.length == 2)
            {
                return Math.max(0, prices[1] - prices[0]);
            }
            
            int[] changes = new int[prices.length];
            changes[0] = 0;
            
            for (int i = 1; i < changes.length; i++)
            {
                changes[i] = prices[i] - prices[i - 1];
            }
            
            int[] maxChange = new int[changes.length];
            
            maxChange[0] = 0;
            
            int maxSoFar = maxChange[0];
            
            for (int i = 1; i < maxChange.length; i++)
            {
                maxChange[i] = Math.max(maxChange[i - 1] + changes[i], changes[i]);
                maxSoFar = Math.max(maxSoFar, maxChange[i]);
            }
            
            return maxSoFar;
        }
    }
    
    // Problem Analysis:
    // Find a day i and a day j for which buying at i and selling at j give the largest profit
    // In other words: find 2 elements prices[i] and prices[j] such that i < j and prices[j] - prices[i] is maximum
    // We first construct an array recording the daily changes in price. Let this array be Changes.
    // Changes[i] = prices[i] - prices[i - 1]
    // To find the largest increase in price between 2 days, we find the contiguous subarray in Changes with the maximum sum
    // 
    // Finding maximum subarray:
    // Let maxChange(i) be the maximum sum out of all subarrays that start from the left and end at i
    // For maxChange(i + 1), there are 2 possible cases:
    // _ The maximum subarray at i + 1 contains only A[i + 1]
    // _ The maximum subarray at i + 1 contains A[i + 1] and the maximum subarray at i
    // Hence, we have: maxChange(i + 1) = max(maxChange(i) + A[i + 1], A[i + 1])
    // Using this recursive relation, we can find the largest change in price (profit) in O(n) using Dynamic Programming

Log in to reply
 

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