Best Time to Buy and Sell Stock系列第三题。之前两题分别说可以买卖任意多次和只能买卖一次。
此题是买卖两次。
买卖两次，找个节点分割问题，就把问题变成两个买卖一次的问题。但是超时。时间复杂度要到o(n^2)
另外一个思路。
按照买卖一次的方法处理正序，逆序
然后存储到达每个点时的max值。线性解法。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size() <= 1)return 0;
        vector<int> dis;
        dis.clear();
        for(int i = 0;i < prices.size()-1;i++) {
            int val = prices[i+1] - prices[i];
            dis.push_back(val);
        }
        vector<int> cost;
        cost.clear();
        if(dis[0] <= 0) {
            cost.push_back(0);
        }
        else {
            cost.push_back(dis[0]);
        }
        for(int i = 1;i < dis.size();i++) {
            if(cost[i-1] + dis[i] >= 0) {
                cost.push_back(cost[i-1] + dis[i]);
            }
            else {
                cost.push_back(0);
            }
        }
        int maxnow = 0;
        for(int i = 0;i < cost.size();i++) {
            if(cost[i] < maxnow)
                cost[i] = maxnow;
            else {
                maxnow = cost[i];
            }
        }</p>

<pre><code>    vector&amp;lt;int&amp;gt; cost_back;
    cost_back.clear();
    if(dis[dis.size()-1] &amp;lt;= 0) {
        cost_back.push_back(0);     
    }
    else {
        cost_back.push_back(dis[dis.size()-1]);
    }
    for(int i = dis.size() - 2;i &amp;gt;= 0;i--) {
        if(cost_back[dis.size()-2-i] + dis[i] &amp;gt;= 0) {
            cost_back.push_back(cost_back[dis.size()-2-i] + dis[i]);
        }
        else {
            cost_back.push_back(0);
        }
    }
    maxnow = 0;
    for(int i = 0;i &amp;lt; cost_back.size();i++) {
        if(cost_back[i] &amp;lt; maxnow)
            cost_back[i] = maxnow;
        else {
            maxnow = cost_back[i];
        }
    }
    int max = 0;
    for(int  i = 0;i &amp;lt; cost.size();i++) {
        if(cost.size() - 2 - i &amp;gt;= 0 &amp;amp;&amp;amp; cost.size() - 2 - i &amp;lt; cost.size()) {
            if(max &amp;lt; cost[i] + cost_back[cost.size()-2-i]) {
                max = cost[i] + cost_back[cost.size()-2-i];
            }
        }
        else {
            if(max &amp;lt; cost[i])
                max = cost[i];
        }
    }
    return max;
}
</code></pre>

<p>};