一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+10, M=110, S=2, INF=2e9;

int n, m;
int a[N];

class DP
{
public:
    int f[N][M][S];

public:
    DP()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void init()
    {
        fill(&f[0][0][0], &f[0][0][0]+N*M*S, -INF);
        for(int i=0;i<=n;++i) f[i][0][0]=0;//第i天，手中无股票，已完成0笔交易，最大利润为0
    }

    int work()
    {
        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]+a[i]);
                f[i][j][1]=max(f[i-1][j-1][0]-a[i], f[i-1][j][1]);
            }
        int ans=0;
        for(int i=0;i<=m;++i)
            ans=max(ans, f[n][i][0]);
        return ans;
    }
}dp;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp.init();
    cout<<dp.work();
}