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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // if (prices.empty()||prices.size() == 1)    return 0;
        // int n = prices.size();
        // vector<vector<int>> dp(2,vector<int>(n,0));//0行表示不持股1行表示持股
        // dp[0][0] = 0;
        // dp[1][0] = -prices[0];
        // for(int j=1;j<n;j++){
        //     dp[0][j] = max(dp[0][j-1],dp[1][j-1]+prices[j]);
        //     dp[1][j] = max(dp[1][j-1],dp[0][j-1]-prices[j]);
        // }
        // return max(dp[0][n-1],dp[1][n-1]);
        if (prices.empty() || prices.size() == 1)    return 0;
        int n = prices.size();
        vector<vector<int>> dp(2, vector<int>(n,
                                              0)); //0行表示不持股1行表示持股
        int dp0 =0,dp1 =-prices[0];
        for (int j = 1; j < n; j++) {
            int cur0 ,cur1;
            cur0 = max(dp1+prices[j],dp0);
            cur1 = max(dp1,dp0-prices[j]);
            dp0 = cur0;
            dp1 = cur1;
        }
        return max(dp0, dp1);

    }
};