连续子数组的最大和升级(二)

知识点贪心 动态规划 数组 双指针

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个

3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组

4.返回的数组不计入空间复杂度计算

数据范围:

1<=n<=10^51<=n<=105

-100 <= a[i] <= 100−100<=a[i]<=100

要求:时间复杂度O(n)O(n)，空间复杂度O(n)O(n)

进阶:时间复杂度O(n)O(n)，空间复杂度O(1)O(1)

        连续子数组的最大和之前做过了，但是这道题难度升级，如果存在多个最大和的连续子数组，要求出其中最长的。题目保证了输入的数组最长的结果只有一个。

        来分析一下这个问题，之前我们使用动态规划思路已经求出了连续子数组的最大和。现在还需要附带最大数组的长度信息。我们在统计最大值的时候，还需要统计最大值的连续子数组的第一个元素的下标和最后一个元素的下标，这样我们才能从数组中拎出我们想要的子数组，而不是简单的只拎出最大连续子数组所有元素相加的和。

        假设我们有了两个变量max_start和max_end分别表示最大且最长连续子数组的起始和结束下标。就需要考虑如何给这两个值赋初始值和在程序中什么位置动态调整这两个值。

        我们来看连续子数组最大和的算法是如何实现的，然后再思考在什么位置上可以动态调整max_start和max_end。

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    for (int i = 1; i < length; i++) {
        if (add > 0) {
            add = add + array[i];
        } else {
            add = array[i];
        }
        if (add > max) {
            max = add;
        }
    }
    return max;
}

        首先，循环外max=array[0]，所以max_start和max_end应该都初始化为array[0]的下标。即max_start=0，max_end=0；

        接着很容易想到，可以在找到比当前max更大的值时给max赋新值的同时，也给max_start和max_end赋新值。

        那么代码变成下面这样。

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    int max_start = 0; //用来记录max的起始坐标
    int max_end = 0; //用来记录max的终止坐标
    for (int i = 1; i < length; i++) {
        if (add > 0) {
            add = add + array[i];
        } else {
            add = array[i];
        }
        if (add > max) {
            max = add;
            max_start = xxx1;
            max_end = xxx2;
        }
    }
    int [] B = new int [max_end - max_start + 1];
    for (int i = max_start, j = 0; i <= max_end; i++, j++) {
        B[j] = array[i];
    }
    return B;
}

        这时候找到了在什么位置动态调整max_start和max_end。 但目前它应该赋什么值还不确定，还需要继续分析。

        因为是在add > max的时候做出上面的变化， add表示的是以当前遍历到元素为尾元素的连续子数组的最大和，其首元素的下标也是动态变化的。说白了add指向的也是一个连续子数组，当add指向的连续子数组比max指向的连续子数组所有元素相加和更大时，用add替换max，同时用add的首尾下标替换max的首尾下标。所以问题转换成求add数组的首尾下标了。 add的尾元素的下标就是当前遍历到的位置，即index。那么其首元素的下标呢？ 目前的程序并没有一个变量存储add首元素的下标值，所以我们还需要借助一个变量来在程序合适的位置动态调整add首元素的下标值。

        程序代表调整后变成

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    int max_start = 0; //用来记录max的起始坐标
    int max_end = 0; //用来记录max的终止坐标
    int add_start= 0; //标记遍历到i位置处，以i为结尾的连续子数组的最大和的第一个数字的下标
    for (int i = 1; i < length; i++) {
        if (add > 0) {
            add = add + array[i];
        } else {
            add = array[i];
            add_start= i;
        }
        if (add > max) {
            max = add;
            max_start = xxx1;
            max_end = xxx2;
        }
    }
    int [] B = new int [max_end - max_start + 1];
    for (int i = max_start, j = 0; i <= max_end; i++, j++) {
        B[j] = array[i];
    }
    return B;
}

        可以看到，变量add_start用来表示add指向的连续子数组的首元素的下标值，我选择了在add<0的时候，需要动态调整add的时候，也顺带调整了add_start的值。

        这时候add的首尾元素下标值都找到了，直接替换上面的xxx1和xxx2即可。

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    int max_start = 0; //用来记录max的起始坐标
    int max_end = 0; //用来记录max的终止坐标
    int add_start= 0; //标记遍历到i位置处，以i为结尾的连续子数组的最大和的第一个数字的下标
    for (int i = 1; i < length; i++) {
        if (add > 0) {
            add = add + array[i];
        } else {
            add = array[i];
            add_start= i;
        }
        if (add > max) {
            max = add;
            max_start = add_start;
            max_end = i;
        }
    }
    int [] B = new int [max_end - max_start + 1];
    for (int i = max_start, j = 0; i <= max_end; i++, j++) {
        B[j] = array[i];
    }
    return B;
}

        到这里，算法的大致框架就全部出来了。但是别忘了，题目要求的是最大且最长的连续子数组。所以需要处理最大值max存在多个的情况。

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    int max_start = 0; //用来记录max的起始坐标
    int max_end = 0; //用来记录max的终止坐标
    int add_start= 0; //标记遍历到i位置处，以i为结尾的连续子数组的最大和的第一个数字的下标
    for (int i = 1; i < length; i++) {
        if (add > 0) {
            add = add + array[i];
        } else {
            add = array[i];
            add_start= i;
        }
        if (add > max) {
            max = add;
            max_start = add_start;
            max_end = i;
        } else if (add == max) {
            if ((i - add_start) > (max_end - max_start)) {
               max_start = add_start;
               max_end = i;
            }
        }
    }
    int [] B = new int [max_end - max_start + 1];
    for (int i = max_start, j = 0; i <= max_end; i++, j++) {
        B[j] = array[i];
    }
    return B;
}

        上面处理了max值相等的情况。

        最后一点小注意事项：由于是要求出最大最长的连续子数组，算法中在处理add的，当add<=0的时候都会重新设置add的值和add_start的值。这其实是不合适的。因为我们现在要求的是最长连续子数组，所以应该把add=0的这一部分也算进来才对。只需要把上面的”add > 0“改成“add >= 0”即可。

        所以最后完整的算法代码是：

public int FindGreatestSumOfSubArray(int[] array) {
    int length = array.length;
    int add = array[0]; //用来保存遍历到i~index区间处连子数组最大值
    int max = array[0]; //用来保存最大值
    int max_start = 0; //用来记录max的起始坐标
    int max_end = 0; //用来记录max的终止坐标
    int add_start= 0; //标记遍历到i位置处，以i为结尾的连续子数组的最大和的第一个数字的下标
    for (int i = 1; i < length; i++) {
        if (add >= 0) {
            add = add + array[i];
        } else {
            add = array[i];
            add_start= i;
        }
        if (add > max) {
            max = add;
            max_start = add_start;
            max_end = i;
        } else if (add == max) {
            if ((i - add_start) > (max_end - max_start)) {
               max_start = add_start;
               max_end = i;
            }
        }
    }
    int [] B = new int [max_end - max_start + 1];
    for (int i = max_start, j = 0; i <= max_end; i++, j++) {
        B[j] = array[i];
    }
    return B;
}