[LeetCode] Best Time to Buy and Sell Stock III Solution

Say you have an array for which the i^th 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).

» Solve this problem

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

[Code]

1:    int maxProfit(vector<int> &prices) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int index =0;  
5:      int max1, max2;  
6:      int max =0;  
7:      for(int i =0; i< prices.size(); i++)  
8:      {  
9:        max1=SearchMax(prices,0,i);  
10:        max2 = SearchMax(prices,i+1, prices.size()-1);  
11:        if(max < max1+max2)  
12:          max = max1+max2;  
13:      }  
14:      return max;  
15:    }  
16:    int SearchMax(vector<int>& prices, int start, int end)  
17:    {  
18:      int max=0;  
19:      int min=INT_MAX;  
20:      for(int i =start; i<= end; i++)  
21:      {  
22:        if(min> prices[i]) min = prices[i];  
23:        int diff = prices[i] -min;  
24:        if(diff> max)  
25:        {  
26:          max = diff;          
27:        }  
28:      }  
29:      return max;  
30:    }  

Update 03/12/2014
Just see the comments. Looks I didn't post the right code.
Line 6~12 and Line 15~21 can be merged into one pass. But keep it for readability.

1:  int maxProfit(vector<int> &prices) {   
2:       if(prices.size() <= 1) return 0;  
3:       vector<int> maxFromLeft(prices.size(), 0);  
4:       vector<int> maxFromRight(prices.size(), 0);  
5:       int minV = INT_MAX, maxP = INT_MIN;  
6:       for(int i =0; i< prices.size(); i++)  
7:       {  
8:            if(minV > prices[i]) minV = prices[i];  
9:            int temp = prices[i] - minV;  
10:            if(temp > maxP) maxP = temp;  
11:            maxFromLeft[i] = maxP;  
12:       }  
13:       int maxV = INT_MIN;  
14:       maxP = INT_MIN;  
15:       for(int i =prices.size()-1; i>=0; i--)  
16:       {  
17:            if(maxV < prices[i]) maxV = prices[i];  
18:            int temp = maxV - prices[i];  
19:            if(temp > maxP) maxP = temp;  
20:            maxFromRight[i] = maxP;  
21:       }  
22:       int maxProfit = INT_MIN;  
23:       for(int i =0; i< prices.size()-1; i++)  
24:       {  
25:            int sum = maxFromLeft[i] + maxFromRight[i+1];  
26:            if(sum > maxProfit) maxProfit = sum;  
27:       }  
28:       if(maxProfit < maxFromRight[0])  
29:            maxProfit = maxFromRight[0];  
30:       return maxProfit;   
31:  }