题目描述：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
1 <= prices.length <= 10^50 <= prices[i] <= 10^5
解法一：动态规划
算法思路：
由于只能进行两次交易，且必须在完成第一笔交易后才能进行第二笔交易，因此，定义以下四个变量：
- buy1：进行了第一次买操作。
- sell1：进行了第一次卖操作，即完成了第一笔交易。
- buy2：进行了第二次买操作。
- sell2：进行了第二次卖操作，即完成了第二笔交易。
对于 buy1 而言，在第 i 天可以不进行任何操作，也可以以 prices[i] 的价格买入股票，那么得到 buy1 的状态转移方程：
$$
\text{{buy}}_1 = \max(\text{{buy}}_1’, -\text{{prices}}[i])
$$
其中buy1’表示第i-1天的状态
对于 sell1 而言，在第 i 天可以不进行任何操作，也可以在进行了第一次买的操作的前提下以 prices[i] 的价格卖出股票，那么得到 sell1 的状态转移方程：
$$
\text{{sell}}_1 = \max(\text{{sell}}_1’, \text{{buy}}_1’ + \text{{prices}}[i])
$$
同理可得到 buy2 和 sell2 的状态转移方程：
$$
\text{{buy}}_2 = \max(\text{{buy}}_2’, \text{{sell}}_1’ – \text{{prices}}[i])
$$
$$ \text{{sell}}_2 = \max(\text{{sell}}_2’, \text{{buy}}_2’ + \text{{prices}}[i]) $$
由于在同一天买入并且卖出这一操作带来的收益为0，不影最终答案，因此状态转移方程可以写为：
$$
\text{{buy}}_1 = \max(\text{{buy}}_1, -\text{{prices}}[i])
$$
$$
\text{{sell}}_1 = \max(\text{{sell}}_1, \text{{buy}}_1 + \text{{prices}}[i])
$$
$$
\text{{buy}}_2 = \max(\text{{buy}}_2, \text{{sell}}_1 – \text{{prices}}[i])
$$
$$
\text{{sell}}_2 = \max(\text{{sell}}_2, \text{{buy}}_2 + \text{{prices}}[i])
$$
最后的答案为 sell2。
代码实现：
class Solution {
public int maxProfit(int[] prices) {
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for(int i = 1; i < prices.length; i++){
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
}
复杂度分析：
时间复杂度： O(n)，其中 n 为数组 prices 的长度。
空间复杂度： O(1)
