一个数组的和最大的连续子数组的和（借鉴别人的收获挺大还有感想）

浏览数：26 / 时间：2015年06月08日

借鉴思路：例如有数组 -1 -3
-4 3 6 -2-6 9 7 5 5 -5 -8首先通过 b<0，b=a[i ]把前三个负数剔除b=-4时b<0此时b=a[3](3)
sum从初值0变为3为到目前为止的最大子数组的和然后只要a[i]>0b+=b[i] 赋值给sum 再出现负数时此时b肯定减小，最大子数组的和仍为sum直到b再次变为负值或者又加到出现了正值（b此时仍为正值）前者给b赋值当前a【i】开始新一轮并把结果与sum比较，后者保持结果累计继续相加与sum比较看是否有更大结果。这样只要有更大结果就赋给sum

代码和注释：

#include <iostream>
#include<time.h>
using namespace std;

int maxSum(int* a, int n)
{
   int sum=0;
   //其实要处理全是负数的情况，很简单，如稍后下面第3点所见，直接把这句改成："int sum=a[0]"即可
   //也可以不改，当全是负数的情况，直接返回0，也不见得不行。
   int b=0;

   for(int i=0; i<n; i++)
   {
     if(b<0)
          b=a[i];
     else
         b+=a[i];
    if(sum<b)
          sum=b;
}
return sum;
}

int main()
{
int n,k=0;
cout<<"请输入数组长度："<<endl;
cin>>n;
    int *a=new int [n];//定义动态数组数组长度可变

   for( int i = 0 ; i < n ; i++)
   {
    a[i] = rand()%20 - 10 ;
   }
   for( int i = 0 ; i < n ; i++)
   {
    cout<<a[i]<<" ";
   }
   cout<<endl;
    for( int i = 0 ; i < n ; i++)//产生的数组都为负数时的情况
   {
   if(a[i]<0)
   {
    k++;
   }
   }
if(n==k)
{
         for( int i = 1 ; i < n ; i++)
        {
   k=a[0];
        if(a[i]>k)
       {
       k=a[i];
       }
        }
    cout<<"最大和为："<<k<<endl;
}
else
{
  cout<<"最大和为："<<maxSum(a,n)<<endl;