最大连续字段和

最大连续子段和的定义

给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。如果该序列的所有元素都是负整数时定义其最大子段和为0

求法1:

第一种当然是暴力枚举每一个子段,求其和比较。这里不再讨论

方法2:

我们知道每一个子区间都可以表示为a[j]-a[i](这里给出C语言的实现代码)

#include<stdio.h>
#include<string.h>
int a[100];
int main()
{
    int i,j,n, sum;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i]+=a[i-1];   /*这里相当一个预处理 ,现在数组中保存的是前i项的和*/
        }
        sum=0;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<=n;j++)
                if(a[j]-a[i]>sum)
                    sum=a[j]-a[i];
        }
        printf("%d\n",sum);
    }
    return 0;
}

接下来是第三种方法:

我们把数组的数从左向右扫描的区间和sum,,然后和结果ans比较。如果sum>ans 则把sum付给ans。如果sum这个我不懂,就不说了。第三种方法代码如下:

#include<stdio.h>

int a[100];
int main()
{
    int ans,sum,i,n;
    while(scanf("%d",&n)!=EOF)
    { 
        ans=sum=0;
        for(i=0;i<n;i++) scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            sum+=a[i];
            if(sum<0)
                sum=0;
            if(sum>ans)
                ans=sum;
        }
        printf("%d\n",ans);
    }
    return 0;
}