数组 a 中有 M 个数 ， 将 M 个数分成 N 组 ， 并且每组中的数据顺序和原数组中的顺序保持一致，求 N 组中的数据之和最大为多少？
向 dp 数组中赋初始值 ，如果 M == N ，则 dp[ i ][ i ] = dp[ i - 1 ][ i - 1 ] + a[ i ] ;
若N为1时 ，即为求连续子串最大和问题；
假设dp[ 1 ][ i ] ( 2 =< i <= M) 代表 与第 i 个数组成连续子串的最大和，当dp[ 1 ][ i - 1 ] < 0 时 ， a[ i ] 独立作为一个子串 ， 即 dp[ 1 ][ i ] = max ( dp[ 1 ][ i -1 ] + a[ i ] , a[ i ] ) ;很需要注意的一点是：dp[ 1 ][ i ] 不一定是 i 个数中连续子串的最大和。
分别求出数组中有一个数、两个数、三个数……M个数中连续子串的最大和，用dp[ i ][ 1 ] 来表示；
若N为2时，表示将M个数分成 2 组 ，求两组数中的和最大 ；
dp[ 2 ][ i ] ( 3 =< i <= M ) 代表 与第 i 个数组成连续子串，形成两个连续子串中，第2个子串的最大和；
可知，第二个子串可以单独成为一段，最终形成两段，也可以和上一个段一起形成一段，最终形成两段；
所以 dp[M][N] 代表 与第M个数组成的连续子串的最大和，但不一定是 M 个数中连续子串的最大和 ；
与第 M 个数组成连续子串时 ，第 M 个数可以与第 M-1 个数组成的子串组合，也可以独立作为一个子串 ， 与 M-1 个数组成的（N-1）组连续子串中最大和组合 ，才能达到分成 N 组的效果；
最后输出dp数组中最大值，即为 N 组中数据之和的最大值；
下面给出相应的代码：
#include<iostream>
using namespace std ;
#define M 100005
#define max(x,y) ((x) > (y) ? (x) : (y))
int a[ M ] , dp[ M ][ M ] ;
int main() {
int k , n ;
while(cin >> k >> n) {
int i ;
for(i = 1 ; i <= n ; i++)
cin >> a[i] ;
memset(dp,0,sizeof(dp)) ;
for(i = 1 ; i <= k ; i++) {
dp[i][i] = dp[i-1][i-1] + a[i] ;
dp[i-1][i] = max(dp[i-1][i],dp[i-1][i-1]) ;
for(int j = i + 1 ; j <= n ; j++) {
dp[i][j] = max(dp[i-1][j-1]+a[j],dp[i][j-1]+a[j]) ;
dp[i-1][j] = max(dp[i-1][j],dp[i-1][j-1]) ;
}
}
int max1 = -(1<<30) ;
for(i = k ; i <= n ; i++)
max1 = max(max1,dp[k][i]) ;
cout << max1 << endl ;
}
return 0 ;
}
上面的代码空间复杂度比较高，但通过观察可以得到，依照滚动数组的思想，让dp数组的行数为2，在两行中循环，这样轻易一改，省去了很多空间：
有木有很强大！！！ 思维决定到效率！！！
#include<iostream>
using namespace std ;
#define M 100005
#define max(x,y) ((x) > (y) ? (x) : (y))
int a[ M ] , dp[ 2 ][ M ] ;
int main() {
int k , n ;
while(cin >> k >> n) {
int i ;
for(i = 1 ; i <= n ; i++)
cin >> a[i] ;
memset(dp,0,sizeof(dp)) ;
int t = 0 ;
for(i = 1 ; i <= k ; i++) {
t = !t ;
dp[t][i] = dp[!t][i-1] + a[i] ;
dp[!t][i] = max(dp[!t][i],dp[!t][i-1]) ;
for(int j = i + 1 ; j <= n ; j++) {
dp[t][j] = max(dp[!t][j-1]+a[j],dp[t][j-1]+a[j]) ;
dp[!t][j] = max(dp[!t][j],dp[!t][j-1]) ;
}
}
int max1 = -(1<<30) ;
for(i = k ; i <= n ; i++)
max1 = max(max1,dp[k&1][i]) ;
cout << max1 << endl ;
}
return 0 ;
}