[C++] O(n) time O(1) space dp solution with comments


  • 8
    W
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            vector<int> full(2, INT_MIN), empty(2, 0), sell(2, 0);
            for (int i = 0; i < prices.size(); i++) {
                full[i % 2] = max(full[1 - i % 2], empty[1 - i % 2] - prices[i]);  
                    // had bought before OR buy today (pay prices[i])
                sell[i % 2] = full[1 - i % 2] + prices[i];  
                    // sell today (get prices[i])
                empty[i % 2] = max(empty[1 - i % 2], sell[1 - i % 2]);  
                    // had sold before yesterday OR sold yesterday
            }
            return max(empty[1 - prices.size() % 2], sell[1 - prices.size() % 2]);
        }
    };

Log in to reply
 

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