Question

题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。

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

看到这道题，很多人都能想到最直观的方法，即枚举出数组的所有子数组并求出它们的和。一个长度为n的数组，总共有n（n＋1）/2个子数组。计算出所有子数组的和，最快也需要O（n²）的时间。通常最直观的方法不会是最优的解法，面试官将提示我们还有更快的算法。

解法一：举例分析数组的规律

我们试着从头到尾逐个累加示例数组中的每个数字。初始化和为0。第一步加上第一个数字1，此时和为1。接下来第二步加上数字-2，和就变成了-1。第三步加上数字3。我们注意到由于此前累计的和是-1，小于0，那如果用-1加上3，得到的和是2，比3本身还小。也就是说从第一个数字开始的子数组的和会小于从第三个数字开始的子数组的和。因此我们不用考虑从第一个数字开始的子数组，之前累计的和也被抛弃。

我们从第三个数字重新开始累加，此时得到的和是3。接下来第四步加10，得到和为13。第五步加上-4，和为9。我们发现由于-4是一个负数，因此累加-4之后得到的和比原来的和还要小。因此我们要把之前得到的和13保存下来，它有可能是最大的子数组的和。第六步加上数字7，9加7的结果是16，此时和比之前最大的和13还要大，把最大的子数组的和由13更新为16。第七步加上2，累加得到的和为18，同时我们也要更新最大子数组的和。第八步加上最后一个数字-5，由于得到的和为13，小于此前最大的和18，因此最终最大的子数组的和为18，对应的子数组是{3,10,-4,7,2}。整个过程可以用表5.2总结如下：

表5.2　计算数组{1,-2,3,10,-4,7,2,-5}中子数组的最大和的过程

把过程分析清楚之后，我们就可以动手写代码了。下面是一段参考代码：

面试的时候我们要考虑无效的输入，比如输入的数组参数为空指针、数组长度小于等于0等情况。此时我们让函数返回什么数字？如果是返回0，那我们又怎么区分子数组的和的最大值是0和无效输入这两种不同情况呢？因此我们定义了一个全局变量来标记是否输入无效。

解法二：应用动态规划法

如果算法的功底足够扎实，我们还可以用动态规划的思想来分析这个问题。如果用函数f（i）表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f（i）]，其中0≤i<n。我们可用如下递归公式求f（i）：

这个公式的意义：当以第i－1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果比第i个数字本身还要小，所以这种情况下以第i个数字结尾的子数组就是第i个数字本身（如表5.2的第3步）。如果以第i－1个数字结尾的子数组中所有数字的和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和。

虽然通常我们用递归的方式分析动态规划的问题，但最终都会基于循环去编码。上述公式对应的代码和前面给出的代码一致。递归公式中的f（i）对应的变量是nCurSum，而max[f（i）]就是nGreatestSum。因此可以说这两种思路是异曲同工。

源代码：

本题完整的源代码详见31_GreatestSumOfSubarrays项目。

测试用例：

- 功能测试（输入的数组中有正数也有负数，输入的数组中全是正数，输入的数组中全是负数）。

- 特殊输入测试（表示数组的指针为NULL指针）。

本题考点：

- 考查对时间复杂度的理解。这道题如果应聘者给出时间复杂度为O（n²）甚至O（n³）的算法，是不能通过面试的。

- 考查对动态规划的理解。如果应聘者熟练掌握了动态规划算法，那么他就能轻松地找到解题方案。如果没有想到用动态规划的思想，那么应聘者就需要仔细地分析累加子数组的和的过程，从而找到解题的规律。

- 考查思维的全面性。能否合理地处理无效的输入，对面试结果有很重要的影响。