Question ：

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

for example： array[]  = { 2, 5, 3, 8, 9, 4 } ， maxProfit = （5-2） + （9-3） = 3 + 6 = 9.

Anwser 1 ：

class Solution {
 public:
     int maxProfit(vector<int> &prices) {
         // Start typing your C/C++ solution below
         // DO NOT write int main() function
         if (prices.size() == 0)
             return 0;
             
         vector<int> f1(prices.size());
         vector<int> f2(prices.size());
         
         int minV = prices[0];
         f1[0] = 0;
         for(int i = 1; i < prices.size(); i++)
         {
             minV = min(minV, prices[i]);
             f1[i] = max(f1[i-1], prices[i] - minV);
         }
         
         int maxV = prices[prices.size()-1];
         f2[f2.size()-1] = 0;
         for(int i = prices.size() - 2; i >= 0; i--)
         {
             maxV = max(prices[i], maxV);
             f2[i] = max(f2[i+1], maxV - prices[i]);
         }
         
         int sum = 0;
         for(int i = 0; i < prices.size(); i++)
             sum = max(sum, f1[i] + f2[i]);
             
         return sum;
     }
 };

说明：

array[]  = { 2, 5, 3, 8, 9, 4 }

f1[] = { 0,



3



, 1, 6, 7, 2 } = { 0, 3, 3, 6, 7, 7 }

f2[] = { 7, 4,



6



, 1, 0, 0 } = { 7, 6, 6, 1, 0, 0 }

max = { 7, 9, 9, 7, 7, 7 }