leetcode 123. 买卖股票的最佳时机 III

使用动态规划的解法，空间复杂度O(2*2)如果交易k次则为O(2*k)，时间复杂度O(2n)，交易k次为O(n*k)，

因此本题实际上可以退化为买卖一次的情况：去掉buy2和sell2，即leetcode121;   以及进化为买卖k次的情况，即状态变量增加为k个buy和sell,即leetcode188

初始化buy[k]=-∞，sell[k]=0;具体原理如下：

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        //当只能持有1股时题目可以认为是一个二维的图计算递推，定义buy1,sell1,buy2,sell2,表示第i天（i为下标）第1或2次买入卖出

        //定义状态转移，见程序

        //为了能够递推需要状态初值，考虑第0天buy1肯定为买入第0天，需要让-price在任何情况下都大于buy1，因此buy1初值为-∞

        //sell1的状态至少是当天买入并卖出，因此最小为0，又因为只要大于0就应该选择大于0的方案，综合两种情况应该赋值为0，同理buy2和sell2

        int len=prices.size();

        if(len<=) return ;

        int sell1=,sell2=,buy1=INT_MIN,buy2=INT_MIN;

        int res=;

        for(int price:prices){

            buy1=max(buy1,-price);

            sell1=max(sell1,buy1+price);

            buy2=max(buy2,sell1-price);

            sell2=max(sell2,buy2+price);

        }

        return sell2;

    }

};