• 效仿 买卖股票3
• 现在需要 buy[k] 和 sell[k]

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

int maxProfit(int k, vector<int>& a) {
    int n = a.size(), inf = 1000000000;
    
    // buy(i) : 第 i 次买完股票后手里的钱, 初始没买过股票, 所以 buy 是 -inf
    // sell(i): 第 i 次卖完股票后手里的钱, 初始没有股票, 所以 sell 是 0
    vector<int> buy(k + 1, -inf);
    vector<int> sell(k + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 思考下这里为何要倒着枚举
        // 正着枚举行不行呢？
        for (int j = k; j >= 1; j--) {
            // 买股票, 手里的钱会变少
            buy[j]  = max(buy[j],  sell[j - 1] - a[i]);  // max(啥也不干, 买股票)
            
            // 卖股票, 手里的钱会变多
            sell[j] = max(sell[j], buy[j]  + a[i]);  // max(啥也不干, 卖股票)
        }
    }
    return sell[k];
}

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