Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

本题要求只能最多买卖两次。

状态定义：f(x, y) -------- 第x笔交易在第y天能取得的最大利润

状态转移：

（1）当x == 1时

        a：我们可以选择在第y天不卖出也不买入，

                a-1：如果此时y == 0，即第0天，那么f(1, 0) = 0，即取得的最大利润为0。

                a-2：如果此时y > 0，那么此时我们的第x笔交易在第y天能取得的最大利润是f(1, y - 1)，因为我们在第y天既不买入也不卖出，取得的最大利润自然和第x笔交易在第y - 1天能取得的最大利润相同。

        b：我们可以选择在第y天卖出，

                b-1：如果此时y == 0，显然，我们不可能在第0天卖出，这种情况不予讨论。

                b-2：如果此时y > 0，f(x, y) = max(prices[y] - prices[b])，其中0 <= b < y，代表我们在第b天买入。

综上，对于x == 1的情况，当y == 0时，f(1, 0) = 0；当y > 0时，f(1, y) = max(f(1, y - 1), prices[y] - prices[b])，0 <= b < y。

（2）当x == 2时

        a：我们可以选择在第y天不卖出也不买入，

                a-1：如果此时y == 0，即第0天，那么f(x, y) = 0，即取得的最大利润为0。

                a-2：如果此时y > 0，那么此时我们的第x笔交易在第y天能取得的最大利润是f(2, y - 1)，因为我们在第y天既不买入也不卖出，取得的最大利润自然和第x笔交易在第y - 1天能取得的最大利润相同。

        b：我们可以选择在第y天卖出，

                b-1：如果此时y == 0，显然，我们不可能在第0天卖出，这种情况不予讨论。

                b-2：如果此时y > 0，f(x, y) = max(prices[y] - prices[b] + f(1, b - 1))，其中0 <= b < y，代表我们在第b天买入。

综上，对于x == 2的情况，当y == 0时，f(2, 0) = 0；当y > 0时，f(2, y) = max(f(2, y - 1), prices[y] - prices[b] + f(1, b - 1))，0 <= b < y。

时间复杂度是O(kn ^ 2)，其中k为交易次数，n为prices数组的大小。空间复杂度是O(kn)。

int maxProfit(vector<int>& prices) {

        //动态规划

        int res = 0;

        if(prices.size() == 0) return res;

        int dp[3][prices.size()];

        for(int k=0; k<prices.size(); k++) dp[0][k] = 0;

        for(int k=1; k<=2; k++){

            dp[k][0] = 0;

            int Min = prices[0];

            for(int i = 1; i < prices.size(); i++){

                dp[k][i] = max(dp[k][i - 1], prices[i] - Min);

                Min = min(Min, prices[i] - dp[k - 1][i - 1]);

            }

        }

        return dp[2][prices.size()-1];

    }