我理解的算法 - 53.最大子数组和（超经典多种解法：强推、动态规划、Kadane算法）

题目

给你一个整数数组 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

暴力解法（超时）

这道题目也是非常经典，虽为简单题，其实如果推敲其中的解题方法，着实不简单，会有很多惊喜，

我们先从题目出发，顺着题目来解，最容易想到的肯定是暴力解法

我们组合出来所有的子数组，并计算其每个子数组的和，然后取最大的值即为答案，直接上代码

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    for(int i = 0; i < nums.length; i++){
        int sum = 0;
        for(int j = i; j < nums.length; j++){
            sum += nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}
1
2
3
4
5
6
7
8
9
10
11

相信这段代码大家都能理解吧，这样做的话，我们的时间复杂度基本上是$O(n^2)$，并且，我们是过不了leetcode的case的，会超时，所以我们必须要另外想办法才行，我们一样先对题目进行观察分析

强推解答法

我们先来看一下上面的暴力法的解法是怎么一个思路，然后再来看怎么优化，大家可以一起来看一下，我们以示例1来看

示例 1：

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

我们把所有的子数组都列出来看，就按照我们上面暴力法循环的顺序列出来，不要嫌麻烦，有用！！！

[-2],[-2,1],[-2,1,-3],[-2,1,-3,4],[-2,1,-3,4,-1],[-2,1,-3,4,-1,2],[-2,1,-3,4,-1,2,1],[-2,1,-3,4,-1,2,1,-5],[-2,1,-3,4,-1,2,1,-5,4]

[1],[1,-3],[1,-3,4],[1,-3,4,-1],[1,-3,4,-1,2],[1,-3,4,-1,2,1],[1,-3,4,-1,2,1,-5],[1,-3,4,-1,2,1,-5,4]

[-3],[-3,4],[-3,4,-1],[-3,4,-1,2],[-3,4,-1,2,1],[-3,4,-1,2,1,-5],[-3,4,-1,2,1,-5,4]

[4],[4,-1],[4,-1,2],[4,-1,2,1],[4,-1,2,1,-5],[4,-1,2,1,-5,4]

[-1],[-1,2],[-1,2,1],[-1,2,1,-5],[-1,2,1,-5,4]

[2],[2,1],[2,1,-5],[2,1,-5,4]

[1],[1,-5],[1,-5,4]

[-5],[-5,4]

[4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其中每一行代表循环的值为i，即第一行为i = 0，第二行为i = 1，每一列为循环j的值，即第一列为j = 0，第二列为j = 1，这样就行程了一个类似的矩阵，从中大家看出来规律了吗，第一行-2为开头的一组子数组中，即$i=0$的时候，$每一个子数组的和=前一个子数组的和+当前循环到的值$，如$[-2,1,-3]$这个子数组的和 $=$ 他前面一个子数组$[-2,1]$的和$+(-3)$，核心公式就有$sum[j]=sum[j-1]+nums[j]$，所以我们代码中会使用sum记录上一个的子数组的sum值，从而套用公式得到答案，我们已经发现这个规律了，但是还是没法解答这道题目，是吗？当然不是，其实这个规律非常有用处，之所以我们发现了这个规律也解不出来这道题目，是因为我们发现的这个公式作用的范围不是在线性的复杂度内去使用的，说白话点就是如果我们可以把这道题目在循环$i$的时候也能套用其公式，就能在线性时间内解答出来了，那么我们来看一下是否有这个可能。

刚刚我们是从$j$的循环方向去找到的规律，这次我们不妨直接从$i$的方向去寻找规律，并且我们为了容易发现规律，我们从最后一个$i$循环的位置开始看，即$[4]$和$[-5],[-5,4]$之间有没有什么规律，仔细看$[-5],[-5,4]$这一组，他们的最大的子数组我们知道是$[-5,4]$，为什么呢？

因为一个数加上了另一个数，如果这个加上的数大于0的话，那么加出来的数肯定比原来的数大，例子中，$-5$ 加的只要是正数那么肯定比$-5$大，这是我们可以发现的一个【规律一】

通过上面的规律我们进而可以推断出一个数加上了另一个数，如果这个加上的数小于等于0的话，那么其加出来的数肯定比原来的数小，即其本身肯定大，这又是一个【规律二】

到这边我们来进行演算一下，$[4]$这一组的话，他肯定是最大的（因为只有他吗还用说），$[-5],[-5,4]$这一组谁大呢？我们就要看其上一个$[4]$这一组，4是正数，那么根据上面的【规律一】，$[-5,4]$肯定比$[-5]$要大

我们继续来看$[1],[1,-5],[1,-5,4]$这一组，我们发现$[1,-5,4]$不就是我们的上一组$[-5,4]$的所有数的和加上了当前的值吗，这个和我们最早找到的核心公式$sum[j]=sum[j-1]+nums[j]$一样的，并且这边的$j$ 已经可以替换成就使用$i$来算了，即这一组$sum[2]=sum[2-1]+nums[2]$，这又是一个【规律三】，注意，这边我们说的是sum，不是所有子数组最大的和

至此，我们把所有规律整合在一起，继续演算$[1],[1,-5],[1,-5,4]$这一组中谁和最大，根据【规律三】和【规律二】，我们知道了$[1,-5,4]$肯定比$[1]$要小，因为根据【规律三】我们把$[1,-5,4]$可以拆分成计算$sum[i-1]+nums[i]，nums[i]就是1，sum[i-1]在这边是-5,4的和即-1$，再根据【规律二】，这边加了-1，即加了一个负数，那么肯定没有其本身大的，所以肯定是$[1]$比较大，但我们能保证$[1,-5]$也比$[1]$小吗？仔细想想是可以的，因为在上一轮我们就算过了$[-5]$没有$[-5,4]$大，所以$[1,-5]$肯定没有$[1,-5,4]$来的大，即$a<b那么a+c<b+c$，这点毋庸置疑吧

那么，依次类推，$[2],[2,1],[2,1,-5],[2,1,-5,4]$，首先根据上一步骤得出的结论，因为上一轮$[1,-5]$和$[1,-5,4]$都没有$[1]$大，所以优先淘汰$[2,1,-5],[2,1,-5,4]$，然后$[2],[2,1]$中，上一轮我们得出的是1大，然后再加上个正数的话，肯定是$[2,1]$的和最大，我们再看$[-1],[-1,2],[-1,2,1],[-1,2,1,-5],[-1,2,1,-5,4]$，淘汰$[-1,2,1,-5],[-1,2,1,-5,4]$，还有别忘了淘汰$[-1,2]$，就看$[-1],[-1,2,1]$，上一轮2,1的和为3，是正数，所以$[-1,2,1]$大，其余的大家可以继续演算，别忘了最后我们取这些结果中最大的即可，

这样演算的结果就是，其实我们每一轮计算的是一种最佳子结构，所以每一轮都计算出来即可

然后我们就能写代码了，代码非常简单

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int sum = nums[n - 1];
    int maxSum = nums[n - 1];
    for(int i = n - 2; i >= 0; i--){
        if(sum <= 0){
            sum = nums[i];
        }else{
            sum += nums[i];
        }

        maxSum = Math.max(sum, maxSum);
    }
    return maxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们也是从后面往前遍历，并且sum和maxSum都先记录为数组最后一个元素，通过记录一个sum值来完成我们的算法即可

其实上面的解法，推论看起来比较繁琐，但是其思路还是很清晰的，直接看代码肯定是看不懂的，所以还是要靠总结规律才行

动态规划

看了上面的解法后，那么动态规划解法又是怎么一回事呢？其实一毛一样，我们一起来规划规划，因为我们已经把上面的规律都摸清楚了，所以动态规划的核心公式也都出来了，所以我们唯一要做的就是将代码中的sum用一个dp数组来替换进行维护即可，看代码

public int maxSubArray(int[] nums) {
	int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];
    for(int i = 1; i < nums.length; i++){
        if(dp[i - 1] <= 0){
            dp[i] = nums[i];
        }else{
            dp[i] = dp[i - 1] + nums[i];
        }
        maxSum = Math.max(dp[i], maxSum);
    }
    return maxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

规划了一下发现不如我们强推的解法，哈哈

Kadane算法

Kadane算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成动态规划的一个例子。

上面的推论其实我们就已经有了kadane算法的影子在里面了，有了上面的推论作为基础，我们可以直接大胆套用这个算法，即如下代码即可

public int maxSubArray(int[] nums) {        
	int sum = nums[0];
    int maxSum = nums[0];
    for(int i = 1; i < nums.length; i++){
        sum = Math.max(sum + nums[i], nums[i]);
        maxSum = Math.max(sum, maxSum);
    }
    return maxSum;
}
1
2
3
4
5
6
7
8
9

这样就更加直接了就出来结果了，是不是有了强推的基础后，再看这个算法就非常的简单了哈，其实思路和上面分析的解法一样的，这样的算法你理解了吗？

最后，还没完哈，其实还有一种分治法也能解这道题目，但是分治法在本题中并不是最优解，但是其又是一种很好的解题的思路，由于分治法理解起来有点难度，所以感兴趣的可以继续看我下一篇文章，会从分治法的思路来分析这道题目。

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