本文主要是介绍【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
这篇关于【100题】第三题(数组（元素可为正数、负数、0）的最大子序列和)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
