求数组的所有子数组的和的最大值

题目描述：

输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为8,-4,6,-1,3,7,2,-3，和最大的子数组为8,-4,6,-1,3,7,2， 因此输出为该子数组的和21。

思路分析：

求一个数组的最大子数组和，如输入的数组为8,-4,6,-1,3,7,2,-3。由于要考虑到时间复杂度，即要尽量减少for的循环遍历次数，我和丹丹讨论了一下，想到了时间复杂度

为O(n)的算法如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<iostream.h> int maxsum(int*a,int n) {     int sum=0;     int c=0;     for(int i=0;i<n;i++)     {         if(c<0)             c=a[i];         else             c+=a[i];         if(sum<c)             sum=c;     }     return sum; } int main() {     int a[8]={8,-4,6,-1,3,7,2,-3};     cout<<maxsum(a,8)<<endl;     return 0; }

　　

运行结果如下：

考虑到数组全是负数的情况，我和丹丹又对程序做了一些改变：

#include <iostream.h>     
#define n 8 
int maxsum(int a[n])      
{    
int max=a[0];       //如果是全负情况，返回最大数     
int sum=0;    
for(int i=0;i<n;i++)    
{    
    if(sum>=0)     //如果加上某个元素，sum>=0的话，就加     
       sum+=a[i];    
   else       
      sum=a[i];  //如果加上某个元素，sum<0了，就不加     
    if(sum>max)    
         max=sum;    
  }    
   return max;    
}       
int main()    
{    
   int a[]={-8,-4,-6,-1,-5,-7,-2,-3};    
   cout<<maxsum(a)<<endl;    
   return 0;    
}    

运行结果：

以上是我们对求数组的所有子数组的和的最大值程序设计的探讨。