一、什么是求最大连续子数列和
首先来看看这是个怎样的问题的，问题描述：一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组的和的最大值。注意：当全是负数的情况时，返回最大的那个负数
二、解题思路
这个问题的思路其实非常简单，从左到右扫描数组，在扫描过程中，记录数组的负数的个数和扫描过中数据中的最大值，并累加每个扫描到的数据的和，假设用变量thisSum（初值为0）保存，如果当前的累加值大于之前的累加值的最大值 （例如用变量sum记录，初值为0），则把当前的最大值保存为最大值（sum = thisSum），如果thisSum小于0，则把thisSum设置为0并重新进行累加。一直这样扫描数组，直到把数组扫描完。
由于thisSum已经小于0，也就是说之前统计的和可以舍弃，因为把当前的元素累加之后，结果反而小了。例如把数组分成三部分AiB，因为A的值大于0，A+i的值小于0，所以如果从B开始从新累加，则其值一定比包括i然后去累加B的结果大，因为i小于0，而B中的和却不一定比在A之前累加的和大。
由于如果数组全是负数时，要返回最大的负数，而从上面所说的说法中，我们可以看到当前累加总和（thisSum）总是与0进行比较，如果小于0则把thisSum置为0，所以当数组全是负数时，thisSum和数组的最大子序列之和（sum）总是为0，而与现实有点不一样，所以就要记录负数的数量，当负数的数量等于元素的个数（即全是负数）时，就要把最大连续子序列和置为最大的负数。这也是前面所说的，在扫描过程中记录负数的个数和最大元素的作用。
三、实现代码
int MaxSum(int* a,int n) { int sum = 0; //用于记录最大的连续子数组和 int flag = 0;//用于记录负数的个数 int MaxNum = *a;//用于记录数组中最大的数 int ThisSum = 0;//用于记录当前的连续子数组和 for(int i = 0; i < n; ++i) { if(a[i] < 0) //如果无素为负数，则把flag的值加1 ++flag; if(MaxNum < a[i]) //记录数组当前的最大值 MaxNum = a[i]; ThisSum += a[i]; //累加更新当前的子数组之和 if(ThisSum > sum) { //若当前连续子数组之和大于记录的子数组之和 //则设置最大连续子数组之和为当前的和 sum = ThisSum; } else if(ThisSum < 0) { //如果当前连续子数组之和小于0，则抛弃之前的连续子数组， //从此元素的下一个元素重新计算连续子数组之和 ThisSum = 0; } } //若全是负数，最大值为数组中的最大无素 if(flag == n) sum = MaxNum; return sum; } 我们再来看看测试结果吧，测试代码如下：
int main() { int a[100] = {1, -2, 3, 10, -4, 7, 2, -5}; cout<<MaxSum(a,8)<<endl; return 0; } 运行结果如下：
从运行结果和测试数据来看，最大的连续子数组应该是3，10，-4，7，2.它们的和就为18.
四、时间复杂度和空间复杂度分析
从代码和上面的解说可以看到，这个算法的时间复杂度只为O(N)，而且常数为1，即只需要扫描一次数组即可完成任务。而且用到的辅助空间也非常少，只有四个变量，空间复杂度为O(1)。
五、完整代码代码下载地址：
https://github.com/ljianhui/Arithmetic
文件名：max_sum_of_continuous_sub_array.cpp
