计算连续子数组的最大和(剑指 Offer 31 题)

编辑:IHGGGG520   来源:TechPush   程序开发   2018-08-09 19:11:38

点击上方“源码共读”,选择“置顶公众号”

关键时刻,第一时间送达!

作者:nanchen2251         來源:简书

https://www.jianshu.com/p/5e1138d519a1

源码共读整理发布,转载请联系作者获得授权

面试 20:计算连续子数组的最大和(剑指 Offer 31 题)

我们上一次推文留下的题目来源于《剑指 Offer》第 31 题:计算连续子数组的最大和。

面试题:输入一个整型数组,数组中有正数也有负数。数组中一个或多个整数形成一个子数组,求所有连续子数组的和的最大值,要求时间复杂度为 O(n)。

比如输入 {1, -2, 3, 10, -4, 7, 2, -5},能产生子数组最大和的子数组为 {3,10,-4,7,2},最大和为 18。

准备测试用例

我们首先准备好测试用例,该题的测试用例也很简单。

1.输入错误的值,比如空数组或者空指针,应该抛出异常;

2.输入一个数组,数组包含正数和负数;

3.输入一个数组,数组全是正数;

4.输入一个数组,数组全是负数。

思考程序逻辑

看到本题,最直观的想法肯定是分出输入数组的所有子数组,并对它们一一求和,最后找到最大和对应的子数组。但一个长度为 n 的数组,总共都有 n(n+1)/2 个子数组,最快也需要 O(n²),所以显然不符合题目要求的 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}。

我们还是用表格表示,可能会更加清晰。

表格后确实清晰太多了,可见 我们平时有想法不一定好写代码,但做了表格,思路绝对清晰的多。当然你是大佬,完全是可以舍弃表格建思路的。

用上面的这种思路写代码就是:

public class Test20 {

private static int findTheNumOfSubArray(int[] nums) {    if (nums == null || nums.length == 0)        throw new RuntimeException("the length of input must be large than 0!");    // 用 result 存放返回结果,即最大和    int result = Integer.MIN_VALUE;    // 用 sum 存放当前累

标签: 源码,数组,最大,输入,之前,得到,nums