Link：
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1052
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e3+5;
const LL INF = 0x3f3f3f3f;
LL a[N];
LL dp[N],pre[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
int num = 0;
LL ans = 0;
for(int i = 1; i <= n; i++){
scanf("%lld",&a[i]);
if(a[i] > 0)
{
ans += a[i];
num++;
}
}
if(num <= m)
printf("%lld\n",ans);
else{
for(int i = 1; i <= m; i++){
ans = -INF;
for(int j = 1; j <= n; j++)
{
if(j == 1) dp[j] = a[j];
else dp[j] = max(pre[j-1],dp[j-1])+a[j];
pre[j-1] = ans;
ans = max(ans,dp[j]);
//printf("%lld ",dp[j]);
}
pre[n] = ans;
//puts("");
}
printf("%lld\n",pre[n]);
}
return 0;
}
