• 更简单的方法，考虑如下 $2$ 个事实
  • 买股票，你手里的钱就会变少（因为你要花钱买股票嘛）
  • 买股票，你手里的钱就会变多
• $buy(i)$：表示前 $i$ 天，买完股票 后，手里的钱的最大值
• $sell(i)$：表示前 $i$ 天，卖完股票 后，手里的钱的最大值
• 对于 $buy[i]$ 有：

$$\begin{equation} buy[i] = \left\{ \begin{array}{lr} buy[i - 1], & 不买 a[i] \\ 0-a[i], & 买 a[i] \end{array} \right. \end{equation}$$

• 对于 $sell[i]$ 有：

$$\begin{equation} sell[i] = \left\{ \begin{array}{lr} sell[i - 1], & 不卖 a[i] \\ buy[i-1]+a[i], & 卖 a[i] \end{array} \right. \end{equation}$$

• 由于 $buy[i]$ 和 $sell[i]$ 只与 $buy[i-1], sell[i-1]$ 有关
• 因此，我们可以只用两个变量 $buy$ 和 $sell$

#include <bits/stdc++.h>
using namespace std;

int maxProfit(vector<int>& a) {
    int n = a.size(), inf = 1000000000;
    
    // buy:  买完股票后手里的钱, 初始没买过股票, 所以 buy 是 -inf
    // sell: 卖完股票后手里的钱, 初始没有股票, 所以 sell 是 0
    int buy = -inf, sell = 0;
    for (int i = 0; i < n; i++) {
        
        // 买股票, 手里的钱会变少
        buy  = max(buy,  0 - a[i]);  // max(啥也不干, 买股票)
        
        // 卖股票, 手里的钱会变多
        sell = max(sell, buy  + a[i]);  // max(啥也不干, 卖股票)
    }
    return sell;
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << maxProfit(a) << '\n';
    return 0;
}

• 假设我在第 $i$ 天买入了股票
• 我当然要在后面价格最高的一天卖掉

#include <bits/stdc++.h>
using namespace std;

int maxProfit(vector<int>& p) {
    int n = p.size();
    vector<int> f(n);
    f[n - 1] = p[n - 1];
    for (int i = n - 2; i >= 0; i--) f[i] = max(p[i], f[i + 1]);
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans = max(ans, max(0, f[i + 1] - p[i]));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    cout << maxProfit(p) << '\n';

    return 0;
}