[leetcode]Best Time to Buy and Sell Stock III

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).

 Best Time to Buy and Sell Stock 、Best Time to Buy and Sell StockII 这三道题是一脉相承的，当然这道题是最难的。DP与二分法的结合，实在是太妙了。不明白的可以戳这里。

算法思想：

因为交易分为两次，因此以数组中的每个元素为临界，比如prices[i]，计算出[ 0 ~ i ]区间的最大利润，再计算出[ i ~ n - 1]区间的最大利润，而每个区间的计算方法在 Best Time to Buy and Sell Stock 已经提过了，不再啰嗦。然后这样坐下来，时间复杂度为O(n * n)。

事实上：

 

载自pickless

 

对于点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]，即为题目所求。

 代码如下：

 public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2){
        	return 0;
        }
        int max = 0;//record the biggest profit
        int[] left = new int[prices.length];
        left[0] = 0;
        int leftBuyIn = prices[0];
        for(int i = 1; i < left.length; i++){
        	left[i] = Math.max(left[i - 1], prices[i] - leftBuyIn );
        	leftBuyIn =  Math.min(leftBuyIn, prices[i]);
        }
        int[] right = new int[prices.length];
        right[right.length - 1] = 0;
        int rightSellOut = prices[prices.length - 1];
        for(int i = prices.length - 2; i >= 0; i--){
        	right[i] = Math.max(right[i + 1], rightSellOut - prices[i]);
        	rightSellOut = Math.max(rightSellOut, prices[i]);
        }
        
        for(int i = 0 ; i < prices.length; i++){
       		max = Math.max(max, left[i] + right[i]);
        }
        
        return max;
    }