最大连续和

本文来自 最大连续和 - 博客园

给出一个长度为n的序列A1，A2，A3，...An，求最大连续和。换句话说，要求找到1=<i=<j=<n，使得Ai+...+Aj尽量大。

题目似乎很简单，但是在n非常大的时候（如n>10000）时，采用最习惯使用的暴力过的话似乎就有一些难度，

下面逐步给出了几种方法，解决问题在可以解出来时，应该找求最优解

##方法一：枚举

直接在i到j之间一一枚举。复杂度O(n^3)

#include<stdio.h>
 int main()
 {
     int a[1000],n;
     while(scanf("%d",&n)!=EOF)
     {
         int i;
         for(i=0;i<n;i++)
             scanf("%d",&a[i]);
         int j,k,best=a[0];//初始化最大值
         for(i=0;i<n-1;i++)
             for(j=i;j<n;j++)
             {
                 int s=0;
                 for(k=i;k<=j;k++)s+=a[k];
                 if(best<s)best=s;
             }
         printf("%d\n",best);
     }
     return 0;
 }

##方法二：处理后枚举 连续子序列的和等于两个前缀和之差。复杂度O(n^2)

#include<stdio.h>
 int main()
 {
     int n,a[1000],s[1000];
     while(~scanf("%d",&n))
     {
         int i,j;
         for(i=0;i<n;i++)
             scanf("%d",&a[i]);
         int best=a[0];
         s[0]=0;
         for(i=0;i<n;i++)s[i+1]=s[i]+a[i];//递归求前缀和S
         for(i=0;i<n;i++)
             for(j=i;j<n;j++)
                 best=best>(s[j+1]-s[i])?best:(s[j+1]-s[i]);
         printf("%d\n",best);
     }
     return 0;
 }

##方法三：分治法

划分问题：把问题实例划分为子问题
递归求解：递归解决子问题
合并问题：合并子问题的解得到原问题的解
复杂度O(nlogn)

#include<stdio.h>
 int maxsum(int *a,int x,int y)//返回数组左闭右开区间[x，y)中最大连续和
 {
     int i,m,v,L,R,max;
     if(y-x==1)return a[x];//只有一个元素，直接返回
     m=x+(y-x)/2;//分治第一步，划分为[x,m)与[m,y)两部分
     int l=maxsum(a,x,m);//分治第二步，递归求解
     int r=maxsum(a,m,y);
     max=l>r?l:r;
     v=0;L=a[m-1];//第三步，合并子问题
     for(i=m-1;i>=x;i--){v+=a[i];L=L>v?L:v;}
     v=0;R=a[m];
     for(i=m;i<y;i++){v+=a[i];R=R>v?R:v;}
     return max>(L+R)?max:(L+R);//把子问题与L和R比较
 }
 int main()
 {
     int a[1000],n;
     while(~scanf("%d",&n))
     {
         int i;
         for(i=0;i<n;i++)
             scanf("%d",&a[i]);
         int best=maxsum(a,0,n);
         printf("%d\n",best);
     }
     return 0;
 }

##方法四：稍作处理

把O(n^2)的代码稍作处理，得到复杂度O(n)的算法

#include<stdio.h>
 int main()
 {
     int n,a[1000],s[1000];
     while(~scanf("%d",&n))
     {
         int i;
         for(i=0;i<n;i++)
             scanf("%d",&a[i]);    
         s[0]=a[0];
         int maxs=s[0],mins=s[0];
         for(i=1;i<n;i++)
         {
             s[i]=s[i-1]+a[i];
             maxs=maxs>s[i]?maxs:s[i];
             mins=mins<s[i]?mins:s[i];
         }
         printf("%d\n",maxs-mins);
     }
     return 0;
 }