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;

    }

};