面试现场:求连续子数组的最大和及其下标
收藏

点击上方“薛勤的博客”,选择“置顶公众号”

技术文章第一时间送达!

题目

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

举例

输入:2, -3, 4, 5,  -9

输出:9

和最大的连续子数组是 {4, 5},结果就是9。

思路

我们先假设和最大连续子数组是从第一个数开始的。初始化和为0。第一步是加上数字2,此时和为2。第二步加上数字-3,此时和为-1。那么问题来了,我们到底要不要加上数字-3呢?分析过程如下:

  1. 加上-3。此时的和为-1,然后由-1继续加下一个数。

  2. 不加-3。也就是意味当前连续子数组就终结于-3之前的数字,下一个连续子数组的和初始化为0,再加上第一个数字-3,和为-3。

由上述分析可知,加上-3,此时累加的子数组和是-1;不加-3,此时累加的子数组和是-3。-1大于-3,为了后续的累加和更大,所以选择加上-3。

接下来,第三步要不要加上数字4,我们依据上面的决策流程继续分析。当加上数字4,此时累加和为4-1=3;不加上数字4,意味着当前连续子数组终结于数字4之前,此时的累加和初始化为0,加上数字4后和等于4。显而易见,4大于3,所以我们选择抛弃前面的累加和,由数字4继续开始。

后续步骤省略,总结一番。当我们遍历数组时,对于每个数字,要么与前面的子数组累加,要么作为新子数组的起点,如果累加之后的子数组和小于(或等于)当前数字,我们就选择抛弃前面的累加和,将当前数字作为新子数组的起点。整个过程可以用表格总结如下:

步骤操作累加的子数组和最大的子数组和
1加222
2加-3-12
3抛弃累加的和-1,加444
4加599
5加-909

代码

根据题目要求,我们只需要求出连续子数组的最大和,如果面试官还要求找到连续子数组的起点与终点下标,那么最终的java代码如下:

public class Main {

    public static int child_sum(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }

        int left0 = 0;
        int left1 = 0;
        int right = 0;
        int max = arr[0];
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum <= arr[i]) { //使用<=还是<呢?
                sum = arr[i];
                left0 = i;
            }
            if (sum > max) {
                max = sum;
                left1 = left0;
                right = i;
            }
        }

        System.out.println("left:" + left1 + " right:" + right + " max:" + max);
        return max;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, -345, -9};
        int[] arr2 = new int[]{2, -245, -9};
        int[] arr3 = new int[]{-2, -3, -4, -5, -9};
        child_sum(arr1);
        child_sum(arr2);
        child_sum(arr3);
    }
}

打印输出:

left:2 right:3 max:9
left:2 right:3 max:9
left:0 right:0 max:-2

在上面的代码中使用小于等于或者使用小于有什么区别呢?

假设数组为{2, -2, 4, 5, -9},如果判断条件是小于等于当前数字,那么所得的最大连续子数组为{4, 5}。如果判断条件是小于当前数字,那么所得的最大连续子数组为{-2, 2, 4, 5}。如果对最大连续子数组的长度没有明确要求,使用小于等于进行判断即可。



从求生存到修体系,我在阿里找到了技术人的成长模式

挑战10个最难回答的Java面试题,我第2题就跪了...

阿里面试题:JDBC、Tomcat为什么要破坏双亲委派模型