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 ;
}