题解 | #买卖股票的最好时机（二）#

贪心加动态规划

C++

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
      int res = 0;
      for (int i = 1; i < prices.size(); ++i) {
        if (prices[i] - prices[i - 1] > 0) {
          res += prices[i] - prices[i - 1];
        }
      }
      
      return res;
    }
};