N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。
Input
第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)
第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和
Input示例
7 2
-2
11
-4
13
-5
6
-2
Output示例
26
【分析】dp[j][i]表示从1~i分成j份获得的最大值。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e6+;;
const int M = ;
const int mod = 1e9+;
const int mo=;
const double pi= acos(-1.0);
typedef pair<int,int>pii;
int n,m;
int a[N];
ll dp[][N];
int main(){
scanf("%d%d",&n,&m);
met(dp,);
ll sum=;
int cnt=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>)sum+=a[i],cnt++;
}
if(m>=cnt)return *printf("%lld\n",sum);
int now=;
for(int i=;i<=m;i++){
ll mx=dp[now^][i-];
dp[now][i]=mx+a[i];
for(int j=i+;j<=n-m+i;j++){
mx=max(mx,dp[now^][j-]);
dp[now][j]=max(mx,dp[now][j-])+a[j];
}
now^=;
}
now^=;
ll ans=-;
for(int i=m;i<=n;i++)ans=max(ans,dp[now][i]);
printf("%lld\n",ans); return ;
}