17089 最大m子段和
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
“最大m子段和”问题：给定由n个整数（可能为负）组成的序列a1、a2、a3、...、an，以及一个正整数m，
要求确定序列的m个不相交子段，使这m个子段的总和最大！ m是子段的个数。当m个子段的每个子段和都是负值时，定义m子段和为0。
输入格式
第一行：n和m； （n,m<10000）
第二行：n个元素序列，中间都是空格相连。 比如：
6 3
2 3 -7 6 4 -5
输出格式
输出最大m子段和。 比如：
15 这15可由这三个段之和来的：（2 3） -7 （6） （4） -5
输入样例
6 3
2 3 -7 6 4 -5
输出样例
15
提示
这个题，书上有完整的递归公式分析和源代码P58-59，按照书上的思想就可以完美通过了。 注意一下：书上P58的代码完全准确，但P59的优化代码，引入了c[]数组，但未对c数组全部初始化，
只初始化了c[1]，后面的循环中可能会用到未初始化的某个c元素，从而导致结果不正确。因此用
下面代码替换了书上的c[1]=0;这条语句。
for(int i=0; i<=n; i++) c[i]=0; 我的代码实现：
#include<stdio.h>
#define N 10005
int MaxSum(int m,int n,int *a){
if(n<m||m<)return ;
int *b=new int[n+];
int *c=new int[n+];
b[]=;
for(int i=;i<=n;i++){
c[i]=;
}
for(int i=;i<=m;i++){
b[i]=b[i-]+a[i];
c[i-]=b[i];
int max=b[i];
for(int j=i+;j<=i+n-m;j++){
b[j]=b[j-]>c[j-]?b[j-]+a[j]:c[j-]+a[j];
c[j-]=max;
if(max<b[j])max=b[j];
}
c[i+n-m]=max;
}
int sum=;
for(int j=m;j<=n;j++)
if(sum<b[j])sum=b[j];
return sum;
} int main(){
int x[N];
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&x[i]);
}
printf("%d",MaxSum(m,n,x));
return ;
}