最大子数组问题Kadane算法
写这篇文章的目的是分享自己在解Leetcode题目“最大子数组问题”时候，用到的Kadane算法，这是一个典型的动态规划算法示例。
为了更好的理解Kadane算法，本文章首先介绍暴力破解的方法，然后通过对暴力破解算法的改进，详细介绍Kadane算法的思路，其中会简单介绍动态规划算法。 希望能够帮助读者更好地理解Kadane算法，从而对动态规划算法有更深的理解。
目录
1. 问题描述
LeetCode上面的题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-subarray
在解释Kadane算法之前，我们先从简单的方法入手，首先介绍一下暴力破解的方法。本篇文章就以LeetCode题目中的示例数组为例来介绍算法。
2. 暴力破解
首先观察题目可以很自然地想到一个明显的解决方法：遍历所有的子数组并计算子数组的和，从所有子数组和中找到最大的和，即为结果。这个方法很符合我们的直觉，那么如何遍历所有的子数组呢？直观的办法是从第一个元素开始，查找所有以nums[0]起始的子数组，然后在依次查找以num[1],nums[2]…nums[n-1]起始的所有子数组，具体如下：
nums[0]起始子数组: nums[1]起始子数组:
-2, 1, -3, 4, -1, 2, 1, -5, 4 -2, 1, -3, 4, -1, 2, 1, -5, 4
-2 1,
-2, 1 1, -3
. . ...
. .
. .
1, -3, 4, -1, 2, 1, -5
-2, 1, -3, 4, -1, 2, 1, -5 1, -3, 4, -1, 2, 1, -5, 4
-2, 1, -3, 4, -1, 2, 1, -5, 4上面介绍的方法就可以遍历给定数组的所有子数组了，不过为了方便下文介绍从暴力破解推导Kadane算法的过程，我们对这个遍历方法做个改变，改成从后往前遍历。即：从最后一个元素开始，查找所有以nums[n-1]结束的子数组，为了方便描述用subarray[n-1]表示，然后依次查找以nums[n-2], nums[n-3]…nums[0]结束的子数组（subarray[n-2], subarray[n-3]…subarray[0]），具体如下：
subarray[n-1]: subarray[n-2]:
-2, 1, -3, 4, -1, 2, 1, -5, 4 -2, 1, -3, 4, -1, 2, 1, -5, 4
4 -5
-5, 4 1, -5
. . ...
. .
. .
1, -3, 4, -1, 2, 1, -5, 4 -2, 1, -3, 4, -1, 2, 1, -5
-2, 1, -3, 4, -1, 2, 1, -5, 4,显然，这种办法也可以遍历到nums数组的所有可能的子数组，通过这种暴力破解的方法就很容易得到答案了。下面放出我的代码，这里我使用递归，能更直观的理解第二种遍历方法：
def maxSubArray(self, nums: list, n: int) -> int:
if n==0:
return 0 # in case there is no item in nums
if n==1:
return nums[0]
max_sum, idx = self.maxSubArray(nums[0:n-1], n-1), n-1
s = 0
while idx >= 0:
s += nums[idx]
max_sum = max(s, max_sum)
idx -= 1
return max_sum相信你也看到了，这种算法并不高效，随着数组规模扩大（n增大），子数组的数量也会快速增加，从而使的算法的时间复杂度快速增加。这个算法的时间复制度是$O(n^2)$, 是种比较低效的方法。
那么我们可以如何提高这个算法的效率呢？相信你也想到了，从我的递归程序里面可以看出，这个题目是可以用动态规划来优化的，接下来我们来看看如何使用动态规划解决这个问题。
3. 从暴力破解到Kadane算法的思路过程
动态规划是一种利用空间换时间的算法思想，本质上是通过将一个复杂的求解最优方案的问题，分解成若干个子问题，而问题最终解可以通过子问题的解推导得到。因而我们可以保存子问题的解，在遇到相同子问题时直接从存储中读取解，而不是从新求解子问题，从而达到利用空间换时间的效果。
可以用动态规划求解的问题一般有两个性质：最优子结构和重复子问题。
让我们来分析一下这个题目是否可以使用动态规划的方法求解，首先回忆一下刚刚的递归过程，对于元素i，我们不妨定义subarray[i]为以i元素结尾的所有子数组集合,S[i]表示以i为结尾所有子数组和的集合，sum[i][j]表示以j开头i结束的子数组和（$S[i] \in sum[i][j]$），进而可以定义max_sum[i]表示以i结尾的最大子数组和：
-2, 1, -3, 4, -1, 2, 1, -5, 4 | -2, 1, -3, 4, -1, 2, 1, -5, 4
| 2 2 sum[5][5]
-1 -1 sum[4][4] | -1, 2 1 sum[5][4]
4, -1 3 sum[4][3] | 4, -1, 2 5 sum[5][3]
-3, 4, -1 0 sum[4][2] | -3, 4, -1, 2 2 sum[5][2]
1, -3, 4, -1 1 sum[4][1] | 1, -3, 4, -1, 2 3 sum[5][1]
-2, 1, -3, 4, -1 -1 sum[4][0] | -2, 1, -3, 4, -1, 2 1 sum[5][0]
------ ------- - - | -------- --------- - -
\/ \/ | \/ \/
subarray[4] S[4] | subarray[5] S[5]
max_sum[4] = 3 max_sum[5] = 5递归公式如下：
max_sum[i] = max(sum[i][0], sum[i][1] ...sum[i][i])
final_max = max(max_sum[i], max_sum[i-1])再来观察一下sum[i][j]，可以得到如下规律：
sum[i][i] = nums[i]
sum[i][i-1] = nums[i] + sum[i-1][i-1]
sum[i][i-2] = nums[i] + sum[i-1][i-2]
...
sum[i][0] = nums[i] + sum[i-1][0]我们可以看出sum[i][j]是可以通过sum[i-1][j]推导得到，其中计算sum[i][j]的过程中包含了大量重复计算的子问题sum[i-1][j]，到此我们可以看出这个问题符合动态规划的两个特征，可以用动态规划来解决这个问题，具体如何优化呢？
我们来观察一下递归公式中的max_sum[i]以及上面推导的sum[i][j]的计算过程，很容易可以得到以下公式：
max_sum[i] = max(nums[i], max[i-1]+nums[i])即所有以i结尾的子数组的和的最大值max_sum[i]可以从nums[i]和max[i-1]+nums[i]这两个数中选最大的一个，从而最大子数组和的问题可以转化为递归地计算$max_sum$的子问题上来,而且可以很容易的得出max_sum[0]=nums[0]。因此，可以很自然的得到以下动态规划状态转移方程：
max_sum[i] = max(nums[i], max[i-1]+nums[i])
final_max = max(max_sum[i], final_max)4. Python代码
至此，我们已经分析了这个问题从暴力破解到动态规划算法的优化过程，下面我贴出我自己的python代码，仅供参考：
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) <= 0:
return 0
final_max = nums[0]
max_sum = 0
for n in nums:
max_sum = max(n, max_sum+n)
final_max = max(max_sum, final_max)
return final_max这里我没有用数组存储max_sum[i]，而是直接用了一个变量来存储，由于状态转移过程只需要用到上一个位置的最优结果，因此只存储上一个max_sum是可行的，这样也节约了存储。可以看出优化后的程序，我们只需要遍历一次nums数组，时间复杂度为$O(n)$，比暴力求解了较好的提高。
5. 总结
由于问题的最终解final_max通过分解成max_sum[0]….max_sum[n-1]这些子问题来求解，其中包含了很多重复子问题，这个问题可以用动态规划来优化。通过对Kadane算法的分析，我们可以更好地理解动态规划的思想。