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

题目

输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为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 加2 2 2
2 加-3 -1 2
3 抛弃累加的和-1,加4 4 4
4 加5 9 9
5 加-9 0 9

代码

根据题目要求,我们只需要求出连续子数组的最大和,如果面试官还要求找到连续子数组的起点与终点下标,那么最终的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, -3, 4, 5, -9};
        int[] arr2 = new int[]{2, -2, 4, 5, -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}。如果对最大连续子数组的长度没有明确要求,使用小于等于进行判断即可。

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。