C++ DP Solution, 12ms, with explanation and example


  • 8
    H
    class Solution {
    public:
     int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        int *dpLeft = new int[prices.size()+1]; dpLeft[0] = 0;
        int tmp = prices[0];
        for(int i = 1; i<prices.size(); i++){
            tmp = min(tmp, prices[i]);
            dpLeft[i] = max(dpLeft[i-1], prices[i]-tmp);
        }
        int *dpRight = new int[prices.size()]; dpRight[prices.size()-1] = 0;
        tmp = prices[prices.size()-1];
        for(int i = prices.size()-2; i>=0; i--){
            tmp = max(tmp, prices[i]);
            dpRight[i] = max(dpRight[i+1], tmp-prices[i]);
        }
        tmp = 0;
        for(int i = 0; i<prices.size()-1; i++){
            tmp = max(tmp, dpLeft[i]+dpRight[i+1]);
        }
        tmp = max(tmp, dpLeft[prices.size()-1]);
        return tmp;
    }
    };
    
    • We can combine DP solution and Divide And Conquer Solution here. I will explain this with a simple example.Assume the stock is: 5,4,6,3,4,2,1,6. It is easy to understand that the max profit is 2(6-4)+5(6-1)=7.
    • here, I use two array to cache profit, dpLeft and dpRight.
    • dpLeft: cache the profit from left to right, the stock [5,4,6,3,4,2,1,6] generate dpLeft:[0,0,2,2,2,2,2,5]
    • dpRight: cache the profit from right to left, stock [5,4,6,3,4,2,1,6] generate dpRight:[5,5,5,5,5,5,5,0]
    • then, we use divide and conquer, the stock[5,4,6,3,4,2,1,6] , we compute profit from i = 0 to i = 7, and the maxProfit = max(maxProfit, dpLeft[i]+dpRight[i+1])
    • finally, we finish this computation, the result is 7. the complexity is O(3n)=O(n)

  • 0
    N
    This post is deleted!

  • 0
    Q

    Very clever!


  • 0
    J

    int *dpLeft = new int[prices.size()+1];
    Why the size is "prices.size()+1" rather than "prices.size()"?


Log in to reply
 

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