题目： 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
例1：
输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
思路： 首先考虑单次交易时，需要扫描整个股票价格数组，同时记录两个数值 -> 最小的成本价格； -> 卖出后最大的收益。
对于每个时刻的股票价格（第一个价格除外，因为第一个价格无法作为售出价格，只能作为默认的成本价），都需要考虑如果此时卖出时收益多少，同时更新最低成本价。 伪代码: 最低成本价格 = prices[0]; 最大收益 = 0； forEach prices { 最大收益 = Max{最大收益， prices[i] - 最低成本价格}； 最低成本价格 = Min{最低成本价格， prices[i]}; } 这样扫描一次，就可以得到单次交易的最大收益。
如果需要交易两次，那么需要确定一个界限mid，在[0, mid]存在一个最大收益的交易点，而[mid, len - 1]也存在。而这个界限mid可能存在于[1, len -2] 中的任何地方。 那么我们可以定义两个数组，分别记录当mid在不同位置时，[0, mid]和[mid, len - 1]两个区域的最大收益之和。 由于mid的位置是动态的，因此两个区间的最大收益位置需要分别从两侧开始扫描。参考如下代码：
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) { return 0; } int len = prices.length; int[] startToEnd = new int[len]; int minCost = prices[0]; // 从左侧到右侧扫描每个位置记录可能的最大收益 for (int i = 1; i < len; i++) { startToEnd[i] = Math.max(startToEnd[i - 1], prices[i] - minCost); minCost = Math.min(minCost, prices[i]); } int[] endToStart = new int[len]; int maxSellPrice = prices[len - 1]; // 从右侧到左侧扫描每个位置记录可能的最大收益 for (int i = len - 2; i >= 0; i--) { endToStart[i] = Math.max(endToStart[i + 1], maxSellPrice - prices[i]); maxSellPrice = Math.max(maxSellPrice, prices[i]); } // 假设单次交易即可达到最大收益 int maxProfit = Math.max(startToEnd[len - 1], endToStart[0]); // 用默认单次交易可得到的最大收益与mid存在于[1, len -2]中每一点时两次交易的综合对比 for (int i = 1; i < len - 1; i++) { maxProfit = Math.max(startToEnd[i] + endToStart[i + 1], maxProfit); } return maxProfit; } }