题解 | #买卖股票的最好时机(三)#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // 看答案的
        int n=prices.size();
        // 这里为什么要初始化为最小值呢？，初始化为0为什么会错？？？
        vector<vector<int>> dp(n,vector<int>(5,-10000));
        // 第一天未持有
        dp[0][0] = 0;
        // 第一天持有
        dp[0][1] = -prices[0];

        for(int i=1; i<n; ++i)
        {
            // step1: 第一支股票都还没买入
            dp[i][0] = dp[i-1][0];
            // step2: 第一支股票买入; 但还未卖出
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
            // step3: 第一支股票卖出; 那可能是之前卖出，或者是今天卖出;
            dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
            //step4: 第二支股票买入; 但还未卖出,那可能是之前买入，或者今天买入;
            dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]); 
            // 第二支股票卖出;
            dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        // 最多可以买卖两支股票，那买卖一支也可以，所以要比较一支跟两支哪个结果大
        return max(dp[n-1][2], dp[n-1][4]);

        // 参考 买卖股票的最好时机(二)，选取dp[n-1][0]和dp[n-2][0]，即最后两次不持股的两个最大值
        // 这样做也是错的，这样做区别只是有没有算上第n天而已；
        // int n = prices.size();
        // vector<vector<int>> dp(n,vector<int>(2,0));
        // // 第一天不持股
        // dp[0][0] = 0;
        // // 第一天持股
        // dp[0][1] = -prices[0];

        // for(int i=1; i<n; ++i)
        // {
        //     // 卖掉是赚钱
        //     dp[i][0] = max(dp[i-1][0],dp[i-1][i]+prices[i]);
        //     // 买入是输钱
        //     dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
        // }

        // return dp[n-1][0] + dp[n-2][0];

        // 错误的思路：不是每次遇到降序就卖，有可能后面升得更高
        // 方法一： 用数组对升序段进行保存，让后选取两段最大的就行；
        // 方法二：用两个变量表示最大的两段升序段；
        // int t_1 = 0;
        // int t_2 = 0;

        // int temp = 0;
        // for(int i=1; i<prices.size(); ++i)
        // {
        //     if(prices[i]>prices[i-1])
        //         temp += (prices[i]-prices[i-1]);
               
        //     if(prices[i]<prices[i-1] || (i==prices.size()-1 && temp!=0))
        //     {
        //         // t_1改变的时候，t_2也得改变，保存为原来t_1的值，即第二大值
        //         if(temp > t_1)
        //         {
        //             t_2 = t_1;
        //             t_1 = temp;
        //         }
        //         else if(temp > t_2)
        //             t_2 = temp;
        //         cout << i << ", " << temp << ", " << t_1 << ", " << t_2 <<endl;
        //         // 重置temp
        //         temp = 0;
        //     }
        // }

        // return t_1+t_2;
    }
};