Best Time to Buy and Sell Stock III
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 (ie, you must sell the stock before you buy again).
算法分析：
DP+二分：
正向遍历，用一个一维数组left[i]表示0 ~ i 的最大收益
逆向遍历，用一个一维数组right[i] 表示 i ~ length - 1的最大收益
最后求出最大的left[i] + right[i]
对于点j+1，求price[0..j+1]的最大profit时，很多工作是重复的，在求price[0..j]的最大profit中已经做过了。
类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从price[0..j]推出price[0..j+1]的最大profit。
但是如何从price[j..n-1]推出price[j+1..n-1]？反过来思考，我们可以用O(1)的时间由price[j+1..n-1]推出price[j..n-1]。
最终算法：
数组l[i]记录了price[0..i]的最大profit，
数组r[i]记录了price[i..n]的最大profit。
已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。
最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。
代码如下：
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if(prices == null || prices.length < 2) return 0; 4 int length = prices.length; 5 int[] left = new int[length]; 6 int[] right = new int[length]; 7 int buyIn = prices[0],sellOut = prices[length - 1]; 8 for(int i = 1; i < length; i++){ 9 left[i] = Math.max(left[i - 1], prices[i] - buyIn); 10 buyIn = Math.min(prices[i],buyIn); 11 } 12 for(int i = length - 2; i >= 0; i--){ 13 right[i] = Math.max(right[i + 1], sellOut - prices[i]); 14 sellOut = Math.max(prices[i],sellOut); 15 } 16 int res = 0; 17 for(int i = 0; i < length; i++){ 18 res = Math.max(res, left[i] + right[i]); 19 } 20 return res; 21 } 22 }
[leecode]Best Time to Buy and Sell Stock III
原文：http://www.cnblogs.com/huntfor/p/3937750.html