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.

 

1 public class Solution { 2     public int maxProfit(int[] prices) { 3         if(prices == null || prices.length == 0){ 4             return 0; 5         } 6          7         int[] firstProfit = new int[prices.length]; 8         int min = prices[0]; 9         for(int i =1; i < prices.length; i++){10             min = Math.min(min, prices[i]);11             firstProfit[i] = Math.max(firstProfit[i-1], prices[i] - min);12         }13         14         int result = 0;15         int rightPeek = prices[prices.length-1];16         for(int i = prices.length-1; i >=0; i--){17             rightPeek = Math.max(rightPeek, prices[i]);18             result = Math.max(result, firstProfit[i] + rightPeek - prices[i]);19         }20         return result;21     }22 }