• 效仿 买卖股票1
• 我们依然可以只用 $2$ 个变量解决问题

#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,  sell - 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;
}

• $dp(i, 0)$: 前 $i$ 天, 手上 没有 股票的最大钱数
• $dp(i, 1)$: 前 $i$ 天, 手上 有 股票的最大钱数

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

int maxProfit(vector<int>& p) {
    int n = p.size();

	// dp(i, 0): 前 i 天, 手上 没有 股票的最大钱数
	// dp(i, 1): 前 i 天, 手上   有 股票的最大钱数
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 0, dp[0][1] = -p[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + p[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - p[i]);
    }
    return dp[n - 1][0];
}

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

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

    return 0;
}