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 ;

}