1. 123

best-time-to-buy-and-sell-stock-iii

--

2. 算法

• DP：O(n)

分析：动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit[i]，和第i天之后进行一次交易的最大收益postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

3. 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;

        int n=prices.size();
        vector<int> preprofile(n);
        vector<int> postprofile(n);

        int curmin=prices[0];
        for(int i=1;i<n;i++){
            curmin=min(curmin,prices[i]);
            preprofile[i]=max(preprofile[i-1],prices[i]-curmin);

        }

        int curmax=prices[n-1];
        for(int i=n-2;i>=0;i--){
            curmax=max(curmax,prices[i]);
            postprofile[i]=max(postprofile[i+1],curmax-prices[i]);
        }

        int maxprofile=0;
        for(int i=0;i<n;i++){
            maxprofile=max(maxprofile,preprofile[i]+postprofile[i]);
        }
        return maxprofile;




    }
};