Share my c++ solution, 8ms, O(1) space, dp


  • 0
    Z
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int buy[3] = {INT_MIN, INT_MIN, INT_MIN}, sell[3] = {0,0,0};
            int sz = prices.size();
            if(sz == 0) return 0;
            for(int i=0; i<sz; i++) {
                buy[(i+2)%3] = max(buy[(i+1)%3], sell[i%3]-prices[i]);
                sell[(i+2)%3] = max(sell[(i+1)%3], buy[(i+1)%3]+prices[i]);
            }
            return sell[(sz+1)%3];
        }
    };

Log in to reply
 

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