读完本文，你可以去力扣拿下如下题目：

53.最大子序和

-----------

最大子数组问题和前文讲过的 经典动态规划：最长递增子序列 的套路非常相似，代表着一类比较特殊的动态规划问题的思路：

其实第一次看到这道题，我首先想到的是滑动窗口算法，因为我们前文说过嘛，滑动窗口算法就是专门处理子串/子数组问题的，这里不就是子数组问题么？

但是，稍加分析就发现，这道题还不能用滑动窗口算法，因为数组中的数字可以是负数。

滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串，但关键是，你得清楚地知道什么时候应该移动右侧指针来扩大窗口，什么时候移动左侧指针来减小窗口。

而对于这道题目，你想想，当窗口扩大的时候可能遇到负数，窗口中的值也就可能增加也可能减少，这种情况下不知道什么时机去收缩左侧窗口，也就无法求出「最大子数组和」。

解决这个问题需要动态规划技巧，但是 dp 数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义 dp 数组：

nums[0..i] 中的「最大的子数组和」为 dp[i]。

如果这样定义的话，整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢？按照数学归纳法，假设我们知道了 dp[i-1]，如何推导出 dp[i] 呢？

如下图，按照我们刚才对 dp 数组的定义，dp[i] = 5 ，也就是等于 nums[0..i] 中的最大子数组和：

那么在上图这种情况中，利用数学归纳法，你能用 dp[i] 推出 dp[i+1] 吗？

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。

所以说我们这样定义 dp 数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义 dp 数组的含义：

以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全部发布在 labuladong的算法小抄，持续更新。建议收藏，按照我的文章顺序刷题，掌握各种算法套路后投再入题海就如鱼得水了。

这种定义之下，想得到整个 nums 数组的「最大子数组和」，不能直接返回 dp[n-1]，而需要遍历整个 dp 数组：

依然使用数学归纳法来找状态转移关系：假设我们已经算出了 dp[i-1]，如何推导出 dp[i] 呢？

可以做到，dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：

综上，我们已经写出了状态转移方程，就可以直接写出解法了：

以上解法时间复杂度是 O(N)，空间复杂度也是 O(N)，较暴力解法已经很优秀了，不过注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，那么我们可以进行「状态压缩」，将空间复杂度降低：

虽然说动态规划推状态转移方程确实比较玄学，但大部分还是有些规律可循的。

今天这道「最大子数组和」就和「最长递增子序列」非常类似，dp 数组的定义是「以 nums[i] 为结尾的最大子数组和/最长递增子序列为 dp[i]」。因为只有这样定义才能将 dp[i+1] 和 dp[i] 建立起联系，利用数学归纳法写出状态转移方程。

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的 在线电子书 有 100 篇原创文章，手把手带刷 200 道力扣题目，建议收藏！对应的 GitHub 算法仓库 已经获得了 70k star，欢迎标星！