图解算法——最大子序和(2)

1、题目描述

见 https://www.cnblogs.com/gjmhome/p/15110730.html

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这里分享一下进阶解法，上篇文章我们知道了一般解法，时间复杂度为O(n)，空间复杂度为O(1)。

2、进阶解法

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

说到分治法，我们首先想到的是二分法，二分法是典型的运用分而治之的思想的一种方法。

我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l, r] 区间内的最大子段和，那么最终我们要求的答案就是 get( nums, 0, nums.size() - 1)。

那么如何分治实现这个操作呢？对于一个区间 [l, r]，我们取 m = (l+r)/2 ，对区间 [l, m] 和 [m+1, r]分治求解。

当递归逐层深入直到区间长度缩小为 1 的时候，递归开始回升。这个时候我们考虑如何通过 [l, m] 区间的信息和 [m+1, r] 区间的信息合并成区间 [l, r]的信息。

这里最关键的问题有两个：

我们要维护区间的哪些信息呢？
我们如何合并这些信息呢？

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

lSum 表示 [l, r] 内以 l 为左端点的最大子段和；
rSum 表示 [l, r] 内以 r 为右端点的最大子段和；
mSum 表示 [l, r] 内的最大子段和；
iSum 表示 [l, r] 的区间和；

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

首先最好维护的是 iSum，区间 [l ,r] 的 iSum = 左子区间的 iSum + 右子区间的 iSum ；
对于 [l, r] 的 lSum , lSum = max{ 左子区间的 lSum , (左子区间的 iSum + 右子区间的 lSum) }；
对于 [l, r] 的 rSum，rSum = max{ 右子区间的 rSum , (左子区间的 rSum + 右子区间的 iSum) }；
当计算好上面三个变量后，就很好计算 [l, r] 的 mSum 了。

我们可以考虑 [l, r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l, r] 的 mSum 可能是「左子区间」的 mSum 和「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和「右子区间」的 lSum 求和。三者取大。

3、实现

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);
    }
}

复杂度分析：

时间复杂度为：O(N)；
空间复杂度为：O(logN)；

4、扩展

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

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

Over.......