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];
}
