最大子序和

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

前言

语文中的总分总到了算法中是什么样的？今天带大家看看分治法。分而治之，化整为零，化繁为简，也不失为一种解决问题的良方秘药。

题目

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

子数组 是数组中的一个连续部分。

分析

上次我们使用动态规划法解决了这个问题，标准答案还有一种分治法，今天我们来研究一下。

分治法顾名思义，即分为治之，也就是将一个大的问题，分成许多小的问题来解决。 例如[-2,1,-3,4,-1,2,1,-5,4]

大致图就是这样，把整体拆成部分，分别比较左节点的值和右节点的值以及左右节点和的值的大小，将三者最大的值向上返回。

值得注意的是当左边的返回的最大值和右边返回的最大值中间跨了别的值的时候，计算左右节点的和的时候需要把中间跨越的值加进去。比如上如中【-2，1，3】推选的最大值是1；而【4，-1】推选的最大值是4；4和1并不是连续的，中间跨越了一个数-3，所以我们计算和的时候需要sum=1+(-3)+4=2

最后返回的最大的结果就是我们要找的值。

答案

• lSum 表示 [l,r] 内以 l 为左端点的最大子段和，也就是上图的left
• rSum 表示 [l,r] 内以 r 为右端点的最大子段和,也就是上图的right
• mSum 表示 [l,r] 内的最大子段和也就是上一层的left或者right
• iSum 表示 [l,r] 的区间和,也就是上图的sum、

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)。需要为递归提供栈空间。

总结

分而治之，通过递归，将大的数组变成一个个小的数组，形成一个二叉树的结构，分别秋每个叶子节点的最大值、叶子节点的和，以及三者对比的最大值。如果最后根节点下的两个叶子节点最大值的分支是连续的，那么这个连续的数组就是我们要找的最大子数组。

• Divide:

  先分。将问题ABC分为AB,C两个子数组求最大子数组的问题。针对AB继续递归将其变成分别对A,B两个子数组求最大子数组的问题。

• Conquer:

  后治。分别对A，B,C求解。

• Combine:

  最后再合并，最终的问题就转换为求A,B,C三类子数组中的最大者,问题也就解决了。

这让我想到了语文中的一种写法叫做总分总。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！

\