昨天碰到的一道笔试题，求代码解

给定n个整数的数组a[]（有正有负），求其最大连续子段和。例如：{-2，11，-4，13，-5，-2}，得到结果为11+（-4）+13=20.复杂度为O(n)才能得满分。

int maxSum(int a[], int n, int &start, int &len)//start记录开始位置，len记录长度
{
int sum = a[0], temp = a[0];
start = 0, len = 1;
for (int i = 1; i < n; i++)
{
if (temp < 0)
{
temp = a[i];
start = i;
}
else
temp += a[i];
if (temp > sum)
{
sum = temp;
len = i - start + 1;
}
}
return sum;
}

《编程之美》上有这个题

老题了

C/C++ code

int max_sub1( int a[  ],int size)
{
     int i,j,v,max=a[ 0 ];
     for ( i=0;i<size;i++ )
     {
          v=0;
          for ( j=i;j<size;j++ )
          {
               v += a[ j ];
               if ( v>max )
                    max=v;
          }
     }
     return max;
}

int max_sub2( int a[  ],int size )
{
     int i,max=0,sum=0;
     for ( i=0;i<size;i++ )
     {
          sum += a[ i ];
          if ( sum >max )
               max=sum;
          else if ( sum<0 )
               sum =0;
     }
     return max;
}

int max_sub3( int a[  ],int size)
{
     int i,max=0,sum=0;
     for ( i=0;i<size;i++ )
     {
          if ( sum >0 )
               sum += a[ i ];
          else
               sum=a[ i ];
          if ( sum >max )
               max=sum;
     }
     return max;
}