121. 买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int GlobalMax = INT_MIN;
    int Min = INT_MAX;
    int Max = INT_MIN;
    for (int i = 0; i < prices.size(); ++i) {
      int P = prices[i];
      if (P < Min) {
        Min = P;
        Max = Min;
      }
      if (P > Max)
        Max = P;
      GlobalMax = max(GlobalMax, Max - Min);
    }
    return GlobalMax;
  }
};

以后注意一下，但凡你最后想返回 *std::max_element() 都得想想你到底需不需要。其实一个 GlobalValue 就解决了。

这道题的关键点其实就在于「只能在未来卖出」这个限制条件。如果没有这个限制条件，那就比较烦人了——就变成一个求最大差值的 DP 问题了。

二刷

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int GlobalMax = 0;
    int Min = INT_MAX;
    int Max = INT_MIN;
    for (int X : prices) {
      // We want to buy as low as possible, so every time we encounter a lower
      // price, reset our decision.
      if (X < Min) {
        Max = X;
        Min = X;
      }
      if (X > Max)
        Max = X;
      GlobalMax = std::max(GlobalMax, Max - Min);
    }
    return GlobalMax;
  }
};

评论区有个这个解释可正视听。其实我这个解法还不是特别简洁，虽然比较直观吧，但是官解也非常好：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

这里的 minprice 能够奏效的原因就在于，我们每天都假设自己可以买入，而且我们仅仅遍历这个数组一遍。事实上，如果遍历这个数组多次，我们很可能是得不到正确结果的，因为会出现时间上的回溯，比如官方示例当中，就会出现所谓的 \(7-1=6\) 的情况。换句话说，这道题不是「能用贪心解」，而是「只能用贪心解」。

不过官解这个 1e9 有点吓人了。其实看下题目要求，1e4 就行了。

三刷

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int MaxProfit = 0;
    int LowestPrice = prices.front();
    for (int X : prices) {
      // Reset the price. That's why it's called greedy.
      if (X < LowestPrice)
        LowestPrice = X;
      MaxProfit = max(MaxProfit, X - LowestPrice);
    }
    return MaxProfit;
  }
};

根本不用什么1e9、1e4，直接取最前元素作为初始最小值就好了。