给定长度为N的序列S。定义sum(i , j) = s[i] + ... + s[j]。给定m，求m段sum(i1, j1) + ... + sum(im,jm)。且没有ix <= iy <=jx。
Input
输入m，输入n。输入n个数。
Output
输出最大和
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
思路1：dp[i][j]:前j个数分成i组
dp[i][]j]=max(a[j],dp[i][j]+a[j],dp[i-1][k]+a[j]),k<i;
思路2：f[j]代替dp[i-1][k];
但是思路1在时间和空间上会超时；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxa=1e6;
using namespace std;
#define inf 1<<30
int m,n,a[maxa];
int f[maxa],dp[maxa];
int main(){while(~scanf("%d%d",&m,&n)){for(int i=0;i<n;i++) scanf("%d",&a[i]); //注意初始化int mm;memset(f,0,sizeof(f));memset(dp,0,sizeof(dp)); for(int i=0;i<m;i++){mm=-inf;for(int j=i;j<n;j++){dp[j]=max(dp[j-1]+a[j],f[j-1]+a[j]);f[j-1]=mm;mm=max(dp[j],mm);}}printf("%d\n",mm);}return 0;
}