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

本文主要是介绍【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));