题解 | 买卖股票的最好时机(四)

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

int main() {
    int n, k;
    cin >> n >> k;
    if (n < 2 || k == 0) {
        cout << 0 << endl;
        return 0;
    }

    if (k >= n / 2) {
        long long profit = 0;
        int prev, cur;
        cin >> prev;
        for (int i = 1; i < n; i++) {
            cin >> cur;
            if (cur > prev) profit += (cur - prev);
            prev = cur;
        }
        cout << profit << endl;
        return 0;
    }
    vector<long long> buy(k + 1, LLONG_MIN / 4), sell(k + 1, 0);
    for (int i = 0, p; i < n; i++) {
        cin >> p;
        for (int t = 1; t <= k; t++) {
            buy[t] = max(buy[t], sell[t - 1] - p);
            sell[t] = max(sell[t], buy[t] + p);
        }
    }
    cout << sell[k] << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")