算法--连续子数组的最大和

题

输入一个整型数组（正、负数均有），数组中一个或连续的多个整数组成一个子数组，求所有子数组的最大值。
要求时间复杂度为 O(n)
例：输入数组为{1, -2, 3, 10, -4, 7, 2, -5}, 和最大的子数组为{3, 10, -4, 7, 2}, 因此输出为该子数组的和为18

分析

最直接的解法：枚举所有子数组并求它们的和。长为n的数组，共有 n*(n + 1)/2 个子数组。计算出所有子数组之和，最快需要 O(n^2)，显然不符合要求

思路一 举例分析数组规律

通常，举例能够具象化算法，让你能够更直观的看到问题，解算法题时，碰到不好解决的问题，可以尝试举例分析问题规律，降低问题难度

从头到尾逐个累加例中每个数字。初始化和为0：

1. 加1 和为1
2. 加-2 和为-1
3. 加3 上一步的累积和为负数，那么我们不用考虑之前的累积和，从第一个数字开始的子数组也不用考虑 —— 从第三个数开始重新累加 和为3
4. 加10 和为13
5. 加-4 和为9 —— 因为-4为负，加上-4后会是累加和变小，所以可以把上一步的13当做暂时发现的最大子和值
6. 加7 和为16，比之前的最大值13大，更新Result为16
7. 加2 和为18，更新Result为18
8. 加-5 和为13

依据上述步骤，可以确定最大子和是18

思路二 应用动态规划

应用递归思想

f(i) = pData[i] if i == 0 or f(i - 1) <= 0
      else f(i - 1) + pData[i]

当以第i-1个数字结尾的子数组中所有数字之和小于0时，如果把这个负数与i个数累加，得到的结果比第i个数本身还要小，所以这种清空下以第i个数字结尾的子数组就是第i个数字本身；
如果以第i-1个数字结尾子数组中所有数字的和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和

用递归的方式分析动态规划问题，最终都是使用循环解决

SourceCode – C++

bool g_invalideINput = false;

int FindGreatestSumOfSubArray(int* pData, int nLength){
  if(pData == NULL || nLength <= 0){
    g_invalideINput = true;
    return 0;
  }

  g_invalideINput = false;

  int nCurSum = 0;
  int nGreatestSum = 0x80000000;
  for(int i = 0; i < nLength; ++i){
    if(nCurSum <= 0) nCurSum = pData[i];
    else nCurSum += pData[i];

    if(nCurSum > nGreatestSum)
      nGreatestSum = nCurSum;
  }
  return nGreatestSum;  
}