数组 a 中有 M 个数 ， 将 M 个数分成 N 组 ， 并且每组中的数据顺序和原数组中的顺序保持一致，求 N 组中的数据之和最大为多少？
先分析，若N为1时 ；即为求连续子串最大和问题；
假设dp[ i ][ 1 ] 代表 与第 i 个数组成连续子串的最大和，当dp[ i-1 ][ 1 ] < 0 时 ， a[ i ] 独立作为一个子串 ， 即 dp[ i ][ 1 ] = max ( dp[ i-1 ][ 1 ] + a[ i ] , a[ i ] ) ;很需要注意的一点是：dp[ i ][ 1 ] 不一定是 i 个数中连续子串的最大和。
所以 dp[M][N] 代表 与第M个数组成的连续子串的最大和，但不一定是 M 个数中连续子串的最大和 ；
与第 M 个数组成连续子串时 ，第 M 个数可以与第 M-1 个数组成的子串组合，也可以独立作为一个子串 ， 与 M-1 个数组成的（N-1）组连续子串中最大和组合 ，才能达到分成 N 组的效果；
最后输出dp数组中最大值，即为 N 组中数据之和的最大值；
下面给出相应的代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<iostream>using
namespace std ;
#define max(x,y) ((x) < (y) ? (y) : (x))int main() {
int
k , n ;
cin >> k >> n ;
int
a[105] = {0} ;
int
i ;
for(i = 1 ; i <= n ; i++)
cin >> a[i] ;
int
dp[105][105] = {0} ;
dp[1][1] = a[1] ;
int
max1 = -10000 ;
for(i = 1 ; i <= k ; i++) {
int
max2 = -10000 ;
for(int
j = i ; j <= n ; j++) {
max2 = max(max2,dp[j-1][i-1]) ;
dp[j][i] = max( dp[j-1][i] + a[j] , max2 + a[j] ) ;
}
}
for(i = k ; i <= n ; i++)
max1 = max(max1,dp[i][k]) ;
cout << max1 << endl ;
return
0 ;
} |