最大子数组和Java实现代码示例_Java

一、题目

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组[4,-1,2,1]的和最大，为6。

示例 2：输入：nums = [1]输出：1

示例 3：输入：nums = [5,4,-1,7,8]输出：23

1 <= nums.length <= 105-104 <= nums[i] <= 104

进阶： 如果你已经实现复杂度为o(n)的解法，尝试使用更为精妙的 分治法 求解。

二、代码

【1】动态规划： 假设nums数组的长度是n，下标从0到n−1。我们用f(i)代表以第i个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：max⁡0≤i≤n−1{f(i)}因此我们只需要求出每个位置的f(i)，然后返回f数组中的最大值即可。那么我们如何求f(i)呢？我们可以考虑nums[i]单独成为一段还是加入f(i−1)对应的那一段，这取决于nums[i]和f(i−1)+nums[i]的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：f(i)=max⁡{f(i−1)+nums[i],nums[i]}不难给出一个时间复杂度o(n)、空间复杂度o(n)的实现，即用一个f数组来保存f(i)的值，用一个循环求出所有f(i)。考虑到f(i)只和f(i−1)相关，于是我们可以只用一个变量pre来维护对于当前f(i)的f(i−1)的值是多少，从而让空间复杂度降低到o(1)，这有点类似「滚动数组」的思想。

class solution {
    public int maxsubarray(int[] nums) {
        int pre = 0, maxans = nums[0];
        for (int x : nums) {
            pre = math.max(pre + x, x);
            maxans = math.max(maxans, pre);
        }
        return maxans;
    }
}

时间复杂度： o(n)，其中n为nums数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度： o(1)。我们只需要常数空间存放若干变量。

【2】分治： 这个分治方法类似于「线段树求解最长公共上升子序列问题」的pushup操作。也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。

我们定义一个操作get(a, l, r)表示查询a序列[l,r]区间内的最大子段和，那么最终我们要求的答案就是get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间[l,r]，我们取m=⌊l+r2⌋，对区间[l,m]和[m+1,r]分治求解。当递归逐层深入直到区间长度缩小为1的时候，递归「开始回升」。这个时候我们考虑如何通过[l,m]区间的信息和[m+1,r]区间的信息合并成区间[l,r]的信息。最关键的两个问题是：

1、我们要维护区间的哪些信息呢？

2、我们如何合并这些信息呢？

对于一个区间[l,r]，我们可以维护四个量：

1、lsum表示[l,r]内以l为左端点的最大子段和

2、rsum表示[l,r]内以r为右端点的最大子段和

3、msum表示[l,r]内的最大子段和

4、isum表示[l,r]的区间和

以下简称[l,m]为[l,r]的「左子区间」，[m+1,r]为[l,r]的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l,r]的信息）？对于长度为1的区间[i,i]，四个量的值都和nums[i]相等。对于长度大于1的区间：

1、首先最好维护的是isum，区间[l,r]的isum就等于「左子区间」的isum加上「右子区间」的isum。

2、对于[l,r]的lsum，存在两种可能，它要么等于「左子区间」的lsum，要么等于「左子区间」的isum加上「右子区间」的lsum，二者取大。

3、对于[l,r]的rsum，同理，它要么等于「右子区间」的rsum，要么等于「右子区间」的isum加上「左子区间」的rsum，二者取大。

4、当计算好上面的三个量之后，就很好计算[l,r]的msum了。我们可以考虑[l,r]的msum对应的区间是否跨越m——它可能不跨越m，也就是说[l,r]的msum可能是「左子区间」的msum和「右子区间」的msum中的一个；它也可能跨越m，可能是「左子区间」的rsum和「右子区间」的lsum求和。三者取大。

这样问题就得到了解决。

class solution {
    public class status {
        public int lsum, rsum, msum, isum;

        public status(int lsum, int rsum, int msum, int isum) {
            this.lsum = lsum;
            this.rsum = rsum;
            this.msum = msum;
            this.isum = isum;
        }
    }

    public int maxsubarray(int[] nums) {
        return getinfo(nums, 0, nums.length - 1).msum;
    }

    public status getinfo(int[] a, int l, int r) {
        if (l == r) {
            return new status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        status lsub = getinfo(a, l, m);
        status rsub = getinfo(a, m + 1, r);
        return pushup(lsub, rsub);
    }

    public status pushup(status l, status r) {
        int isum = l.isum + r.isum;
        int lsum = math.max(l.lsum, l.isum + r.lsum);
        int rsum = math.max(r.rsum, r.isum + l.rsum);
        int msum = math.max(math.max(l.msum, r.msum), l.rsum + r.lsum);
        return new status(lsum, rsum, msum, isum);
    }
}

假设序列a的长度为n。

时间复杂度： 假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为o(log⁡n)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是o(∑i=1log⁡n2i−1)=o(n)，故渐进时间复杂度为o(n)。

空间复杂度： 递归会使用o(log⁡n)的栈空间，故渐进空间复杂度为o(log⁡n)。

题外话： 「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？

对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间[0,n−1]，还可以用于解决任意的子区间[l,r]的问题。如果我们把[0,n−1]分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在o(log⁡n)的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在o(log⁡n)的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。