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

贪心加动态规划

• C++版本

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
      if (prices.empty()) {
        return 0;
      }
      
      int res = 0;
      int min = prices[0];
      
      //  这里买入和卖出不能是同一天，注意语句的顺序
      //  每次比较当天和前n天的差额，取出最大值
      for (int i = 1; i < prices.size(); ++i) {
        res = std::max(res, prices[i] - min);
        min = std::min(min, prices[i]);
      }
      
      return res;
    }
};

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
      if (prices.empty()) {
        return 0;
      }
      
      //  dp[i] 表示前i天（包括i）在内的最大收益
      std::vector<int> dp(prices.size(), 0);
      int min = prices[0];
      
      for (int i = 1; i < prices.size(); ++i) {
        dp[i] = std::max(dp[i - 1], prices[i] - min);
        min = std::min(min, prices[i]);
      }
      
      return dp[prices.size() - 1];
    }
};

C语言版本

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param prices int整型一维数组 
 * @param pricesLen int prices数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maxProfit(int* prices, int pricesLen ) {
  if (pricesLen == 0) {
    return 0;
  }
  int res = 0;
  int min = prices[0];
  
  for (int i = 1; i < pricesLen; ++i) {
    res = res > prices[i] - min ? res : prices[i] - min;
    min = min < prices[i] ? min : prices[i];
  }
  
  return res;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param prices int整型一维数组 
 * @param pricesLen int prices数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maxProfit(int* prices, int pricesLen ) {
  if (pricesLen == 0) {
    return 0;
  }
  
  //  dp[i] 表示前i天（包含i）的最大收益
  int dp[pricesLen];
  for (int i = 0; i < pricesLen; ++i) {
    dp[i] = 0;
  }
  int min = prices[0];
  
  for (int i = 1; i < pricesLen; ++i) {
    dp[i] = dp[i - 1] > prices[i] - min ? dp[i - 1] : prices[i] - min;
    min = min < prices[i] ? min : prices[i];
  }
  
  return dp[pricesLen - 1];
}