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

 

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

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

 

方法一：枚举

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

1 #include
     
       2 int main() 3 { 4     int a[1000],n; 5     while(scanf("%d",&n)!=EOF) 6     { 7         int i; 8         for(i=0;i
     

方法二：处理后枚举

连续子序列的和等于两个前缀和之差。复杂度O(n^2)

1 #include
     
       2 int main() 3 { 4     int n,a[1000],s[1000]; 5     while(~scanf("%d",&n)) 6     { 7         int i,j; 8         for(i=0;i
      
       (s[j+1]-s[i])?best:(s[j+1]-s[i]);16         printf("%d\n",best);17     }18     return 0;19 }
      
     

方法三：分治法

划分问题：把问题实例划分为子问题

递归求解：递归解决子问题

合并问题：合并子问题的解得到原问题的解

复杂度O(nlogn)

1 #include
     
       2 int maxsum(int *a,int x,int y)//返回数组左闭右开区间[x，y)中最大连续和 3 { 4     int i,m,v,L,R,max; 5     if(y-x==1)return a[x];//只有一个元素，直接返回 6     m=x+(y-x)/2;//分治第一步，划分为[x,m)与[m,y)两部分 7     int l=maxsum(a,x,m);//分治第二步，递归求解 8     int r=maxsum(a,m,y); 9     max=l>r?l:r;10     v=0;L=a[m-1];//第三步，合并子问题11     for(i=m-1;i>=x;i--){v+=a[i];L=L>v?L:v;}12     v=0;R=a[m];13     for(i=m;i
      
       v?R:v;}14     return max>(L+R)?max:(L+R);//把子问题与L和R比较15 }16 int main()17 {18     int a[1000],n;19     while(~scanf("%d",&n))20     {21         int i;22         for(i=0;i
      
     

方法四：稍作处理

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

1 #include
     
       2 int main() 3 { 4     int n,a[1000],s[1000]; 5     while(~scanf("%d",&n)) 6     { 7         int i; 8         for(i=0;i
      
       s[i]?maxs:s[i];16             mins=mins