1.题目描述

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

2.解法分析

限定了交易次数之后题目就需要我们略微思考一下了，由于有两次交易的机会，那么我们选定一个时间点t_i，将此时间点作为两次交易的支点的话，必然有：

      t₀….t_i之内满足最佳交易原则，t_i-t_n天也满足最佳交易原则，那么这就是一个动态规划的策略了，于是有下面的代码：

 

class Solution {

public:

int maxProfit(vector
           
             &prices) {
           

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(prices.size() <=1)return 0;

vector
           
            ::iterator iter;
           

for(iter=prices.begin();iter!=prices.end()-1;++iter)

{

*iter = *(iter+1) - *iter;

}

prices.pop_back();

vector
           
            accum_forward;
           

vector
           
            accum_backward;
           

int max = 0;

int subMax = 0;

for(iter=prices.begin();iter!=prices.end();++iter)

{

subMax += *iter;

if(subMax > max)max=subMax;

else

if(subMax<0)subMax = 0;

accum_forward.push_back(max);

}

vector
           
            ::reverse_iterator riter;
           

max =0 ;

subMax = 0;

for(riter=prices.rbegin();riter!=prices.rend();++riter)

{

subMax +=*riter;

if(subMax >max)max = subMax;

else

if(subMax<0)subMax=0;

accum_backward.push_back(max);

}

max =0;

int len = accum_forward.size();

for(int i=0;i

{

if((accum_forward[i]+accum_backward[len-i-2])>max)

max = accum_forward[i]+accum_backward[len-i-2];

}

return max>accum_forward[len-1]?max:accum_forward[len-1];

}

};

 

ps:做完题之后提交，发现老是AC不了，有个case总是解决不了，本来以为是自己代码写得有问题，检查了半天没发现错误，于是开始看别人怎么写，结果发现别人AC的代码也过不了，猜想可能系统还是做得不完善，应该是后台的线程相互干扰了，过了一段时间果然同样的代码又可以AC了。在这段过程中，看别人写的代码，发现了一个比我简洁一些的写法，虽然我么你的复杂度是一样的，但是此君代码量比我的小一点，以后学习学习，另外，一直不知道vector还可以预先分配大小，从这个代码里面也看到了，算是有所收获。附代码如下：

class Solution {

public:

int maxProfit(vector
       
         &prices) {
       

// null check

int len = prices.size();

if (len==0) return 0;

vector
       
         historyProfit;
       

vector
       
         futureProfit;
       

historyProfit.assign(len,0);

futureProfit.assign(len,0);

int valley = prices[0];

int peak = prices[len-1];

int maxProfit = 0;

// forward, calculate max profit until this time

for (int i = 0; i

{

valley = min(valley,prices[i]);

if(i>0)

{

historyProfit[i]=max(historyProfit[i-1],prices[i]-valley);

}

}

// backward, calculate max profit from now, and the sum with history

for (int i = len-1; i>=0; --i)

{

peak = max(peak, prices[i]);

if (i

{

futureProfit[i]=max(futureProfit[i+1],peak-prices[i]);

}

maxProfit = max(maxProfit,historyProfit[i]+futureProfit[i]);

}

return maxProfit;

}

};