我理解的算法 - 53.最大子数组和（超经典多种解法：分治法）

题目

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray

题目中的进阶里提到了分治法，那么我们一定要来看看怎么解哈，但是因为分治法在本题中其实并不是最优解，可以看这篇文章【我理解的算法 - 53.最大子数组和（超经典多种解法：强推、动态规划、Kadane算法）】，但是其又是一种很好的解题的思路，所以感兴趣的可以继续看这一解法

分治法

分治法的核心思想是把大的问题分解成小的问题，把小的问题分成最小的问题来解决，所以分是关键思路，治是重要手段，分而治之，可解也

那么对于这道题目，我们怎么使用分治去做呢？我们的目的是求得所有的子数组中最大的，那么我们就来看，我们能不能把所有的子数组进行一下分组，我们可以对整个数组对半分，即把数组从中心点切一刀，分为左半边和右半边，然后再把左半边的数组再对半分，再对半分，再对半分直到分不了了为止，右半边也是一样的操作，即我们切成$[left,mid]和[mid+1,right]$，N多个这样的数组，我们先这样分好，如下图显示的这样

以黄色显示的mid分为左右两份一直切分到不能分为止，这样得到的子数组会像上图那样，这个结构类似于树结构，那么这样一个结构我们按照题目怎么来帮助我们进行解题呢？题目要求我们求最大子数组和，那我们在求的时候就需要所有子数组都算一遍然后看哪个子数组的和最大，那么上面这个结构就能帮我们组合出来所有的子数组，并且能够帮助我们快速的比较出哪个子数组最大，其结构可以看成是一个递归结构，并且我们要知道，对于一个我们以mid分界好的数组中，我们和最大的那个子数组只会坐落在mid的左半边中或mid的右半边中或是横跨了我们的mid即左半边和右半边都占到了，只有这三种情况而已，所以我们分别看这三种情况里面哪一种是有最大的和的，那么每一层递归我们都是获取的最大的和去比较的，最终我们就能得到我们想要的那个最大的和了

下面我们来看一下具体的一个演算过程，我们可以先从最底层的两个结点开始看，如下图

我们可以先看-2这个结点，由于-2这个结点已经没法拆分了，所以其最大和即为其本身，1结点也是一样的，这样的话我们向上看，来到[-2,1]这个结点，这个结点的最大和等于了他下面的三种情况中最大的那个值，即公式为$Max(leftMaxSum,rightMaxSum,crossingMaxSum)$，那么这边$leftMaxSum$和$rightMaxSum$很好求，都是其本身我们已经求过了在刚刚，那么$crossingMaxSum$我们要怎么求它呢？

这边我们可以想像一下，一个横跨了我们mid的子数组，其和要最大的话，那么是不是就等于mid往左找组合出来的连续数组中最大和的值以及mid往右找组合出来的连续数组中最大和的值，把这两个值加起来，即为横跨mid的最大的值了，比如-2,1这个结点，我们的mid是-2，那么mid往左看即和为-2（左边带上mid值计算），所以mid左边最大和是-2，右边为1，左右相加得到-1，所以其$crossingMaxSum$即为-1，最后再来比较leftMaxSum, rightMaxSum, crossingMaxSum哪个最大，这个节点肯定是rightMaxSum最大，即1，这样的话，我们就知道怎么写代码去算了，我们先不急着写代码，我们来整个演算一下看看，下面的步骤如下面这些图所示：

最终我们算出了最大值为6，代码如下：

public int maxSubArray(int[] nums) {
    return getMaxSubSum(nums, 0, nums.length - 1);
}
private int getMaxSubSum(int[] nums, int left, int right){
    if(left == right){
        return nums[left];
    }
    int mid = left + (right - left) / 2;
    int leftMaxSum = getMaxSubSum(nums, left, mid);
    int rightMaxSum = getMaxSubSum(nums, mid + 1, right);
    int crossingMaxSum = getCrossingMaxSum(nums, mid, left, right);
    return Math.max(Math.max(leftMaxSum, rightMaxSum), crossingMaxSum);
}

private int getCrossingMaxSum(int[] nums, int mid, int left, int right){
    int leftMaxSum = nums[mid];
    int tempSum = nums[mid];
    for(int i = mid - 1; i >= left; i--){
        tempSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, tempSum);
    }

    int rightMaxSum = nums[mid + 1];
    tempSum = nums[mid + 1];
    for(int i = mid + 2; i <= right; i++){
        tempSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, tempSum);
    }

    return leftMaxSum + rightMaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

是不是思路还挺清晰的呢，不过这种方式有一个地方不太好，就是我们在找CrossingMaxSum的时候其实还挺耗时的，导致了其时间复杂度其实为$nlogn$的，那么我们能不能再改进了呢，其实是有方法的，官方的这种思路就是比较好的，不过不是很好理解，我为了理解这个思路，也花费了不少时间才想明白哈，由于篇幅比较长了，我们就放在下一篇来一起看一下吧

那么，这样的算法，你理解了吗？

最后还望各位兄弟姐妹们点个赞，关个注，更多的我理解的内容我还会陆续和大家分享的，谢谢大家！