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

#include <iostream>
using namespace std;

int main() {
    int prices[1001]; // 存储价格的数组
    int dp[1001][202]; // 动态规划数组
    int n, k; // n 表示天数，k 表示最多交易次数

    // 输入天数和最多交易次数
    cin >> n >> k;

    // 输入每一天的价格
    for(int i = 1; i <= n; i++) {
        cin >> prices[i];
    }

    dp[1][0] = 0; // 第一天不进行任何交易的利润为0

    // 初始化第一天的动态规划数组
    for(int i = 1; i <= 100; i++) {
        dp[1][2 * i - 1] = -prices[1]; // 第一次买入后的状态
        dp[1][2 * i] = 0; // 不进行任何交易的状态
    }

    // 从第二天开始进行动态规划
    for(int i = 2; i <= n; i++) {
        dp[i][0] = 0; // 第0次交易的利润为0

        // 遍历每一次可能的交易次数
        for(int j = 1; j <= k; j++) {
            // 第j次买入后的最大利润
            dp[i][2 * j - 1] = max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] - prices[i]);
            // 第j次卖出后的最大利润
            dp[i][2 * j] = max(dp[i - 1][2 * j], dp[i - 1][2 * j - 1] + prices[i]);
        }
    }

    // 输出在n天内最多进行k次交易的最大利润
    cout << dp[n][2 * k] << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")