最大连续子序列算法(数组的连续子数组最大和(首尾不相连))

时间:2022-01-12 11:07:12

相关描述:

连续子序列最大和,其实就是求一个序列中连续的子序列中元素和最大的那个。

比如例如给定序列:
{ -5,-2, 11, -4, 13, -5, -8 }
其最大连续子序列为{ 11, -4, 13 },最大和为20。

方法一:暴力 O(n^3)

算法描述:

暴力搞来就是枚举子序列的起点和终点,然后计算这一段的和,再通过不断地更新最大值即可。但是效率太低了。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000;
int a[maxn];
int main()
{
    int n,max;
    while(scanf("%d",&n)&&n!=0)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        max=-1111111;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int sum=0;
                for(int k=i;k<=j;k++)
                {
                    sum+=a[k];
                }
                if(max<sum) max=sum;
            }
        }
       printf("%d\n",max);
    }
    return 0;
}
方法二:优化方法一,预处理O(n^2),其实就是在最开始时加一个数组sum[i]表示前i项的和,效率也不高。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000;
int a[maxn],sum[maxn];
int main()
{
    int n,max;
    while(scanf("%d",&n)&&n!=0)
    {
        a[0]=0;
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        max=-1111111;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int s=0;
                s=sum[j]-sum[i-1];
                if(max<s) max=s;
            }
        }
       printf("%d\n",max);
    }
    return 0;
}
方法三:累计遍历算法O(n),效率很高了。

遍历序列的时候对Sum进行累计,如果Sum累积后小于0的话就把Sum重置,每次更新Sum的最大值。最后便能求出最大值。
其实这个算法就是把序列分为好几块,每一块满足:对于任意k,前k个数的和不会小于0(小于0就没有和后面的数列连续的价值了),当前i个数的和大于最大值时就进行更新,而最大值的左边界就是该块序列的第一个,右边界是第i个。
时间复杂度为O(n),而且可以一边读取一边处理,不需要开数组来存,空间也很省。

代码如下:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100005;
int main()
{
    int t,n;
    while(scanf("%d",&n)&&n!=0)
    {
        int max=-1111111,b=-111111;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            if(b<0) b=t;
            else
            {
                b+=t;
            }
            if(b>max)
              max=b;
        }
        printf("%d\n",max);
    }
}
方法四:动态规划O(n),效率同样很高。

算法思想:
设s[j]表示第j处,以a[j]结尾的子序列的最大和。
注意:dp[j]并不是前j-1个数中最大的连续子序列之和,而只是包含a[j]的最大连续子序列的和。我们求出b[j]中的最大值,即为所求的最大连续子序列的和。
递推公式:dp[j]=max{dp[j],dp[j-1]+a[j]};

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10005;
int a[maxn],dp[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        int max= dp[1]=a[1];
        for(int i=2; i<=n; i++)
        {
            if(dp[i-1]+a[i]>=a[i])
            {
                dp[i]=dp[i-1]+a[i];
            }
            else
            {
                dp[i]=a[i];
            }
            if(max<dp[i])
                max=dp[i];
        }
        printf("%d\n",max);
    }
    return 0;
}

注:有时候还需要找出最大连续子序列的左右界,我这里给出第三种方法的可以求左右界的代码,以HDU1003为例。其余的方法实现,读者可以自己探究。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100005;
int a[maxn];
int main()
{
    int t,n;
    while(scanf("%d",&t)!=EOF)
    {
        for( int k=1;k<=t;k++)
        {
            scanf("%d",&n);
            int max=-1111111,b=-111111;
            int l=1,ll=1,r=1;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                if(b<0)
                {
                    b=a[i];
                    ll=i;
                }
                else
                {
                   b+=a[i];
                }
                if(max<b)
                {
                    max=b;
                    l=ll;
                    r=i;
                }
            }
            if(k<t)
                printf("Case %d:\n%d %d %d\n\n",k,max,l,r);
            else
                printf("Case %d:\n%d %d %d\n",k,max,l,r);

        }
    }
}