Java DP Solution. Time O(n), Space O(1)


  • 0
    Z
        public int maxProfit(int[] prices) {
            // use dp idea to solve this problem
            // m[i] represent i-th day the max profit
            // induction rule: for m[i], there are cases. case 1: dont sell at this day: m[i - 1]
            // case 2: sell at this day: prices[i] - globalMin
            // m[i] = max(m[i - 1], array[i] - globalMin)
            // base case: m[0] = 0
            // maintain a global min to indicate the best buy price
            // time complexity is O(n), only check m[i - 1]
            // space complexity is O(1)
            
            // sanity check
            if (prices == null || prices.length <= 1) {
                return 0;
            }
            int last = 0;
            int min = prices[0];
            for (int i = 1; i < prices.length; i++) {
                last = Math.max(last, prices[i] - min);
                min = Math.min(min, prices[i]);
            }
            return last;
        }
    

  • 0
    Z
    This post is deleted!

  • 0
    Z

    Can you explain how the concept dynamic programming is applied here? Thanks!


  • 1
    Z

    @zhongkong.hu
    Basically m[i] represents the max profit for first i days. So I can use the previous result, which is m[i - 1] to solve m[i]. There are two cases.
    Case1: if you don't sell the stock at i-th day, then you can check what's the max profit in first i - 1 day(m[i - 1]).
    Case2: if you want to sell the stock at i-th day, then the profit will be prices[i] - min.
    Then m[i] should be the max of two cases.


Log in to reply
 

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