题目链接：
设(f[i][j])表示选了(i)段，最后一个数是(j)的最大值。
有简单方程：(f[i][j]=Max(f[i-1][k],f[i][j-1])+a[j](k<j))
第一种是断开成为新一段，第二种是接着上一个。
那么再维护一个前缀最大值(g)就可以做到(O(nm))。
注意滚动优化，空间开不下。
代码：
#include <cstdio>
typedef long long ll;
inline ll Max(const ll a,const ll b){return a>b?a:b;}
int n,m,a[5005];
ll f[2][5005],g[2][5005];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
g[i&1][j]=Max(f[i&1][j]=Max(f[i&1][j-1],g[(i&1)^1][j-1])+a[j],g[i&1][j-1]);
printf("%lld
",g[m&1][n]);
return 0;
}