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

#include<iostream>
#include<algorithm>
using namespace std;
int price[100000], dp[200005][201] = { 0 };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> price[i];
    for(int i = 0;i < k;++i)
        dp[0][2 * i + 1] = -price[0];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = max(dp[i - 1][1], - price[i]);
        for(int j = 2;j <= 2 * k;++j)
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + (j % 2 == 0 ? price[i] : -price[i]));
    }
    cout << dp[n - 1][2 * k];
}