题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

输入格式
第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易数量。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

样例

3 2
2 4 1
(输出2)

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+5;

int f[N][110][2];//天数小于等于i天，交易次数恰好为j次，当前是否手中有股票。
int n,m;
int w[N];//第i天股票的价格

int main(){
    cin >> n >> m;//天数和交易次数上限
    for(int i = 1;i <= n;i++)cin >> w[i];
    memset(f,-0x3f,sizeof f);//初始化为负无穷，状态转移时取max，所以到达不了负无穷的状态，输出结果时需要遍历。
    for(int i = 0;i <= n;i++)f[i][0][0] = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+w[i]);//当前有股由上次没有和上次有转移过来。由于上次有而这次无，完成卖出操作，所以第二维j不是j-1。
            f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);//同上，由于新增买入操作，所以是j-1层转移过来。
        }
    int res = 0;
    for(int i = 0;i <= m;i++)res = max(res,f[n][i][0]);//恰好为j时不需要遍历，至多为j时需要遍历。
    cout << res << endl;
    return 0;
}