An easy dp solution with explaination


  • 2
    S
    /*
     * dp solution: O(n) time, O(n) space 
     * unkeep stock status
     *      sellDP[i] = max(sellDP[i-1], buyDP[i-1] + prices[i]);
     *
     *   keep stock status
     *      buyDP[i] = max(buyDP[i-1], sellDP[i-2] - prices[i]);
    */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        vector<int> sellDP(n, 0), buyDP(n, 0);
        buyDP[0] = -prices[0];
        
        for (int i = 1; i < n; ++i) {
            sellDP[i] = max(sellDP[i-1], buyDP[i-1] + prices[i]);
            if (i >= 2) buyDP[i] = max(buyDP[i-1], sellDP[i-2] - prices[i]);
            else buyDP[i] = max(buyDP[i-1], -prices[i]);
        }
        
        return sellDP[n-1];
    }
    
    /*
     * ==> dp solution
     * ==> deducted to O(n) time, O(1) space
    */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        
        int curSell = 0; // current day, yesterday
        int preSell = 0; // the day before yesterday
        int curBuy = -prices[0]; // current day, yesterday
        for (int i = 1; i < n; ++i) {
            int tmp = curSell;
            curSell = max(curSell, curBuy + prices[i]);
            if (i >= 2) curBuy = max(curBuy, preSell - prices[i]);
            else curBuy = max(curBuy, -prices[i]);
            preSell = tmp;
        }
        
        return curSell;
    }

Log in to reply
 

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