要求：输入一个整型数组，数组里有正数也有负数，数组中一个或连续的多个整数构成一个子数组，求所有子数组的和的最大值。

如：输入的数组为{1，-2，3，10，-4，5，1，-5}，则输出结果为15.

思路一：

最直接的思路,可以用两层for循环解决，用来枚举出所有的子数组的和，但这种方式时间复杂度显然为O（n*n）

此思路代码如下：

int  countGreastSumOfSubArray(int * array,int len){	if(array==NULL||len<0)	{		cout<<"输入的数据不合法"<
     
      sum)//如果currentSum>sum，则更新sum的值				sum=currentSum;//一次外层for循环执行完之后，sum的值为array[i]与其余元素连续子数组的和最大值							  //整个外层for循环执行完之后，sum的值即为整个数组中连续子数组的最大和		}	}	return sum;}
     

思路二：

因为只要求输出子数组和最大的值且连续，因此，很自然想到如果用currentSum表示当前的子数组的和，则如果currentSum<=0，则currentSum+下一个元素的值（用A[i]表示，下同）<=A[i]，所以此时，之前累计的子数组最大和被抛弃，currentSum=A[i]，若currentSum>0，则currentSum+=A[i].，最后比较sum与currentSum的值，若currentSum值大于sum

则，更新sum=currentSum。因为只需将整个数组扫描一次，所以时间复杂度为O(n)。

此思路代码如下：

int  countGreastSumOfSubArray(int * array,int len){	if(array==NULL||len<0)	{		cout<<"输入的数据不合法"<
     
      sum)			sum=currentSum;	}	return sum;}
     

上面的数据运行结果如下：