面试 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 存放当前累加结果
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 如果小于 0，则直接说明不可能是从前面开始的。不加之前的值,直接算当前值
            if (sum < 0) {
                sum = nums[i];
            } else {
                // 如果大于 0，则相加
                sum += nums[i];
            }
            // 如果添加后的值大于之前存放的最大值，则更新最大值
            if (sum > result)
                result = sum;
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums1 = {1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println(findTheNumOfSubArray(nums1));
        int[] nums2 = {1,2,3,4,5};
        System.out.println(findTheNumOfSubArray(nums2));
        int[] nums3 = {-1,-2,-3,-4 -5};
        System.out.println(findTheNumOfSubArray(nums3));
    }
}

分别测试测试用例，测试通过。

最后再说点题外的吧，不少人现在还在找我「模拟面试」，该项活动已经截止很久啦，虽然本宝宝的菜单入口依然还在，那只能说明南尘等空闲一点会继续开放的，所以敬请期待洛~

另外一点，南尘的号可能最近一段时间不会日更了，可能一星期，可能一个月，可能更长…但南尘不会辜负大家的陪伴~