Check LintCode 995. Best Time to Buy and Sell Stock with Cooldown

class Solution {
public:
    /**
     * @param prices: a list of integers
     * @return: return a integer
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        // 是with transition fee 的延续
        //关键是定义状态，（有些累了）
        //global[i]表示前i个元素收益。stay at i-th element 几种情况:
        //
        //1, not sell: global[i] = global[i - 1]
        //2, sell: 又分1种情况
        //1), 前一天必然可买: global[i] = buy[i - 1] + i-1th 天 prices
        //2)
        //分析buy[i],
        //1,没有交易: = buy[i - 1]
        //2,买了(因为有cooldown，需要前一天rest)：= global[i - 2] - prices[i - 1]
        // initial: global[0] = 0; buy[0] = -prices[0].
        int sizeP = prices.size();
        if(sizeP <= 1) {
            return 0;
        }
        vector<int> global(sizeP + 1, 0);
        vector<int> buy(sizeP + 1, 0);
        buy[0] = INT_MIN;
        buy[1] = -prices[0];
        global[1] = 0;
       
        for(int i = 2; i < sizeP + 1; i++){
            global[i] = max(global[i - 1], buy[i -1] + prices[i - 1]);
            buy[i] = max(buy[i - 1], global[i - 2] - prices[i - 1]);
        }
        return global[sizeP];
    }
};