Best Time to Buy and Sell Stock III(Hard)
最佳时间买入卖出股票（最多两次买卖）,而且交易之间没有重叠，那么就divide and conquer。
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: A transaction is a buy & a sell. You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
例子：
{4,4,6,1,1,4,2,5}---最大收益6
{2,3,4,5,1,2,3,4,5,6,7,8,4,5,6} --- ---最大收益10
解题思路1
根据题目要求，最多进行两次股票交易（两次买入，两次卖出），而且手中不能有2只股票，就是不能连续两次买入操作。
所以，两次交易必须是分布在2个区间内，也就是交易动作为：买入卖出，买入卖出。
进而，我们可以划分为2个区间[0,i]和[i,len-1]，i可以取0~len-1。
那么两次买卖的最大利润为：在两个区间的最大收益和的最大利润。
一次划分的最大利益为：Profit[i] = MaxProfit(区间[0,i]) + MaxProfit(区间[i,len-1]);
最终的最大利润为：MaxProfit(Profit[0], Profit[1], Profit[2], ... , Profit[len-1])。
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
// get profit in the front of prices
int[] profitFront = new int[prices.length];
profitFront[0] = 0;
for (int i = 1, valley = prices[0]; i < prices.length; i++) {
//i的最大利润为（i-1的利润）和（当前卖出价和之前买入价之差）的较大那个
profitFront[i] = Math.max(profitFront[i - 1], prices[i] - valley);
valley = Math.min(valley, prices[i]);//更新最低买入价
}
// get profit in the back of prices, (i, n)
int[] profitBack = new int[prices.length];
profitBack[prices.length - 1] = 0;
for (int i = prices.length - 2, peak = prices[prices.length - 1]; i >= 0; i--) {
//i的最大利润为（i+1的利润）和（最高卖出价和当前买入价之差）的较大那个
profitBack[i] = Math.max(profitBack[i + 1], peak - prices[i]);
peak = Math.max(peak, prices[i]);//更新最高卖出价
}
// add the profit front and back
int profit = 0;
for (int i = 0; i < prices.length; i++) {
profit = Math.max(profit, profitFront[i] + profitBack[i]);
}
return profit;
}
解题思路2
public int maxProfit2(int[] prices) {
// these four variables represent your profit after executing corresponding transaction
// in the beginning, your profit is 0.
// when you buy a stock ,the profit will be deducted of the price of stock.
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
// the max profit after you buy first stock
if (firstBuy < -curPrice) firstBuy = -curPrice;
// the max profit after you sell it
if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice;
// the max profit after you buy the second stock
if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice;
// the max profit after you sell the second stock
if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice;
}
return secondSell; // secondSell will be the max profit after passing the prices
}