买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路一：

for循环分割成两组，分别计算最大值

时间复杂度O(n2)

思路二：

五个状态

1、未买

2、买第一支股票（buy1）

3、卖第一支股票（sell1）

4、买第二支股票（buy2）

5、卖第二支股票（sell2）

由于1、始终是0，所以实际后四个状态即刻。

状态转移方程：

buy1 = max(buy1,-price[i]);

sell1 = max(sell1,buy1+price[i]);

buy2 = max(buy2,sell1-price[i]);

sell2 = max(sell2,buy2+price[i]);

由于股票可以在同一天不断买入卖出

所以初始化时

buy1 = -price[0];

sell1 = 0;

buy2 = -price[0];

sell2 = 0;

巴特西