Best Time to Buy and Sell Stock with Cooldown

买了股票需要隔一天才能重新买。

DP Space O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        if(n<=1)return 0;

        vector<int> hold(n),unhold(n);

        hold[0]=-prices[0];
        hold[1]=max(-prices[1],-prices[0]);
        unhold[1]=max(0,prices[1]-prices[0]);

        for(int i=2;i<prices.size();i++)
        {
            unhold[i]=max(unhold[i-1],prices[i]+hold[i-1]);
            hold[i]=max(hold[i-1],unhold[i-2]-prices[i]);
        }
        return unhold.back();
    }
};

看了别人解决方案，才发现可以实现O(1) space!!

想到了O(n)的思路后，O(1)的解决方案很容易想出，替换就好了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        if(n<=1)return 0;

        int hold=max(-prices[1],-prices[0]);
        int prev_sell=0;
        int sell=max(0,prices[1]-prices[0]);

        for(int i=2;i<prices.size();i++)
        {
            hold=max(hold,prev_sell-prices[i]);
            prev_sell=sell;
            sell=max(sell,prices[i]+hold);
        }
        return sell;
    }
};