Buy1[i]表示前i天做第一笔交易买入状态最大收益；Sell1[i]表示前i天做第一笔交易卖出状态组大收益

类型一：只能买卖一次，求最大的收益

题目 LeetCode 121

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) 
        return 0;
    // 对于这类问题，买和卖都只有1次
    // buy的初始化为INT_MIN，sell的初始化为0
    int buy1 = INT_MIN, sell1 = 0;
    for (int i = 0; i < prices.size(); i++) { // 每次股票依次遍历
        // 先买才能卖
        buy1 = max(buy1, -prices[i]);
        sell1 = max(sell1, buy1 + prices[i]);
    }
    return sell1;
}

类型二：只能买卖两次，求最大的收益

题目 LeetCode 123

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) 
        return 0;
    int buy1 = INT_MIN, buy2 = INT_MIN, sell1 = 0, sell2 = 0;
    for (int i = 0; i < prices.size(); i++) {
        buy1 = max(buy1, -prices[i]);
        sell1 = max(sell1, buy1 + prices[i]);
        // 第二次又在第一次的基础上买卖
        buy2 = max(buy2, sell1 - prices[i]);
        sell2 = max(sell2, buy2 + prices[i]);
    }
    return sell2;
}

类型三：买卖k次，求最大的收益

题目 LeetCode 188
当k大于等于股票数量时，相当于无限次买卖
当k小于股票数量时，可有两次买卖扩展成k次买卖
由买卖两次，我们可以得到通式为

buy_k = max(buy_k, sell_k - 1 - prices[i])
sell_k = max(sell_k, buy_k + prices[i])

因此buy和sell需要用一个数组存储

int func(vector<int>& prices)// 这里无限次采用贪心算法，求所有相邻的升序之和
{
    int res = 0;
    for(int i = 1; i < prices.size(); ++i)
    {
        if(prices[i] > prices[i - 1])
            res += prices[i] - prices[i - 1];
    }
    return res;
}
int maxProfit(int k, vector<int>& prices) {
    if(prices.size() <= 1) return 0;
    if(k >= prices.size()) return func(prices); // 当k较大的情况

    vector<int> buy(k + 1, INT_MIN);
    vector<int> sell(k + 1, 0);
    for(int i = 0; i < prices.size(); ++i)// 先遍历每一个价格
    {
        for(int j = 1; j <= k; ++j)// 再遍历选的决策，即次数
        {
            buy[j] = max(buy[j], sell[j - 1] - prices[i]);
            sell[j] = max(sell[j], buy[j] + prices[i]);                
        }
    }
    return sell[k];
}

类型四：买卖无限次，求最大的收益

题目 LeetCode 122

    int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }
        int buy = INT_MIN, sell = 0;
        for (int i = 0; i < prices.size(); i++) {
            // 注意和买卖一次的差别
            buy = max(sell - prices[i], buy);
            sell = max(buy + prices[i], sell);
        }
        return sell;
    }

类型五：买卖含有冷却期，求最大的收益

buy[i]表示在第i天之前最后一个操作是买，此时的最大收益。
sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益。
rest[i]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。

我们写出递推式为：

buy[i]  = max(rest[i-1] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

另外，由于冷冻期的存在，我们可以得出rest[i]=sell[i-1]，这样，我们可以将上面三个递推式精简到两个，其实也可以直接理解为就是只能卖了隔一天才能买，所以递推买的时候要用两天前的数据。

buy[i]  = max(sell[i-2] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])

题目 LeetCode 309

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) {
        return 0;
    }
    int buy = INT_MIN, sell = 0, sell_cache = 0;
    for (int i = 0; i < prices.size(); i++) {
        buy = max(buy, sell_cache - prices[i]);
        sell_cache = sell;
        sell = max(sell, buy + prices[i]);
    }
    return sell;
}