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

Ref:http://fisherlei.blogspot.com/2013/01/leetcode-best-time-to-buy-and-sell_3958.html

http://www.cnblogs.com/jasonC/p/3417722.html

[Thoughts]

前后两遍遍历，算出当前位置之前和之后的最大利润。

One dimensional dynamic planning.
Given an i, split the whole array into two parts:
[0,i] and [i+1, n], it generates two max value based on i, Max(0,i) and Max(i+1,n)
So, we can define the transformation function as:
Maxprofix = max(Max(0,i) + Max(i+1, n))  0<=i<n
Pre-processing Max(0,i) might be easy, but I didn‘t figure an efficient way to generate Max(i+1,n) in one pass.

public class Solution {
    public int maxProfit(int[] prices) {
        
        if(prices == null || prices.length == 0)
            return 0;
            
        int[] max = new int[prices.length];
        int min = prices[0];
        int result = 0;
        
        for(int i = 1; i < prices.length; i++){
            min = Math.min(min, prices[i]);
            max[i] = Math.max(max[i-1], prices[i] - min);
        }
        
        int peek = Integer.MIN_VALUE;
        for(int i = prices.length-1; i >= 0; i--){
            
            peek = Math.max(prices[i],peek);
            result = Math.max(result, peek - prices[i] + max[i]);
        }
        return result;
    }
}

Best Time to Buy and Sell Stock III

原文：http://www.cnblogs.com/RazerLu/p/3552842.html