動态規劃_買賣股票的最佳時機|||_1

1.【問題描述】    買賣股票的最佳時機 III

2.【思路】    參考：Best Time to Buy and Sell Stock III

題目要求是“最多可以完成兩筆交易”。則一共有三種情況：不交易；完成一次交易；完成兩次交易。其中，不交易的最大收益是0，完成一次交易包含當天買入當天賣出的情況，是以“完成一次交易”的方案已經包含了“不交易”，故總共有兩種交易方案：完成一次交易和完成兩次交易。用符号（i, j）表示在第i天到第j天的閉區間内完成一次交易所能獲得的最大收益，其中1<=i<=N-1,i<=j<=N-1。這裡的“完成·一次交易”包含以下幾種情況：

2.1 在第k天買入，且在第k天賣出；i<=k<=j，收益為0

2.2 在第p天買入，且在第q天賣出，i<=p<q<=j  ，此時i<j，收益為prices[q]-prices[p]；

則原問題的解是：max{(1,1)+(1,N), (1,2)+(2,N),..., (1,N)+(N,N)}。此時可以參考  動态規劃_最大子數組||_1

建立數組dp_i[N]，數組元素dp_i[i]是 隻進行一次交易，且在第i天賣出股票時的最大收益，則dp_i[1]=0;  

dp_i[i]=max{dp_i[i-1]+prices[i]-prices[i-1],0}.

建立數組dpi[N]，數組元素dpi[i]=（1, i）。則dpi[1]=0;

dpi[i]=max{dpi[i-1],dp_i[i]}.

建立數組dp_N[N]，數組元素dp_N[i]是 隻進行一次交易，且在第i天買入時的最大收益,，則dp_N[N]=0;

dp_N[i]=max{dp_N[i+1]+prices[i+1]-prices[i],0}.

建立數組dpN[N]，數組元素dpN[i]=（i, N）。則dpN[N]=0;

dpN[i]=max{dpN[i+1],dp_N[i]}.

3.【代碼】

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        int N=prices.size();
        if(N<2) {
            return 0;
        }
        vector<int> dp_i(N,0);
        for(int i=1;i<N;++i) {
            dp_i[i]=dp_i[i-1]+prices[i]-prices[i-1];
            dp_i[i]=dp_i[i]>0?dp_i[i]:0;
        }
        vector<int> dpi(N,0);
        for(int i=1;i<N;++i) {
            dpi[i]=dpi[i-1]>=dp_i[i]?dpi[i-1]:dp_i[i];
        }
        vector<int> dp_N(N,0);
        for(int i=N-2;i>=0;--i) {
            dp_N[i]=dp_N[i+1]+prices[i+1]-prices[i];
            dp_N[i]=dp_N[i]>=0?dp_N[i]:0;
        }
        vector<int> dpN(N,0);
        for(int i=N-2;i>=0;--i) {
            dpN[i]=dpN[i+1]>=dp_N[i]?dpN[i+1]:dp_N[i];
        }
        int res=0;
        for(int i=0;i<N;++i) {
            res=res>=(dpi[i]+dpN[i])?res:(dpi[i]+dpN[i]);
        }
        return res;
    }
};