【100题】第三题(数组（元素可为正数、负数、0）的最大子序列和)

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

例如：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

解题思路：当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。

程序源码：

#include <iostream.h>
int get_sub_sum_max(int *arr, int len)
{
int max, sum;

max = arr[0]; //存储最大子数组 和
sum = 0; //判断 一直相加后 是否为负数 从而影响后面再相加
while (len--)
{
sum += *arr++; //下一个数组 元素 遇到负数 则清零

if (sum >=max)//当加上一个负数时 max 没有改变 观察后面加许多值后有木有 大于 max的
max = sum; //max存储sum 不是零的数后 ，再与下一轮 sum+arr[i] 后相比
else if (sum < 0) //当前的和为负数，则影响下一个数
sum = 0;
}
return max;
}
int main()
{
// int a[10]={1,-8,6,3,-1,5,7,-2,0,1}; //这个数组 必须结果是 20
int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; //这个数组 必须 结果是 18
// int a[10]={-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
printf("%d\n",get_sub_sum_max(a,8));

return 0;
}

int a[8]={ 1, -2, 3, 10, -4, 7, 2, -5};

max=1;sum=1

max=1;sum=-1 -->sum=0

max=3;sum=3

max=13;sum=13

max=13;sum=9

max=16;sum=16

max=18;sum=18

max=18;sum=13

返回 max=18

这里给出了详细解答：http://blog.csdn.net/v_JULY_v/article/details/6444021