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:

解题思路

建立两个数组left和right，分别存储某个元素左边和右边所能获得的最大收益。即left[i]存储从[0, i]范围的最大收益；right[i]存储从[i, len - 1]范围的最大收益。

实现代码

/*****************************************************************    *  @Author   : 楚兴    *  @Date     : 2015/2/22 18:08    *  @Status   : Accepted    *  @Runtime  : 16 ms******************************************************************/#include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {public:    int maxProfit(vector
        
          &prices) {        int len = prices.size();        if (len == 0)        {            return 0;        }        vector
         
           left(len, 0);        vector
          
            right(len, 0); int i = 0; int low = prices[0]; int profit = 0; while (i < len - 1) { if (prices[i] < low) { low = prices[i]; } else if (prices[i] >= prices[i + 1]) { profit = max(profit, prices[i] - low); } left[i] = profit; i++; } profit = max(profit, prices[i] - low); left[i] = profit; int high = prices[i]; profit = 0; while(i > 0) { if (prices[i] > high) { high = prices[i]; } else if (prices[i] <= prices[i - 1]) { profit = max(profit, high - prices[i]); } right[i] = profit; i--; } profit = max(profit, high - prices[i]); right[i] = profit; i = 0; int max_profit = 0; while (i < len) { max_profit = max(max_profit, left[i] + right[i]); i++; } return max_profit; }};int main(){ int num[] = { 1,2,3,4,5,6}; vector
           
             n(num, num + sizeof(num)/sizeof(int)); Solution s; int profit = s.maxProfit(n); cout<
            
             <
            
           
          
         
        
       
      
     

另一种解题思路可参考。