【复试上机】LeetCode-简单-013-Maximum Subarray

13.Maximum Subarray

动态规划

使用动态规划需要的前提：最优子结构性质。

最优子结构性质：

重叠子问题：

用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算。

对每个子问题只解一次， 然后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

通常子问题个数随问题的大小呈多项式增长，因此，用动态规划算法通常只需要多项式时间。

动态规划步骤：

题目

发现这个问题可以用动态规划求解：

最优子结构性质

假设数组A的最大子序和对应一个连续元素组成的数组B。那么数组B的子数组的最大子序和也一定是B的一个连续小部分C。

反证法：如果B的子数组的最大子序不是C，也就是比C的累加和更大，那么把这段替换到B中，就可能产生更大的值，那么B就不是A的最大子序和对应的数组，与假设矛盾。故假上述结论正确。

换句话说上面的结论，在求最大子序和的时候，每加入一个新的A[i]都应该使得总的子序和比单独一个A[i]大才对，否则考虑从A[i]开始寻找新的子段和。当然最终取所有子段和的最大值为最终值。

文字思想：

假设当前数组为A。假设当前最大子段和为b，初值为A[0]。

通过我们上面分析的最优子结构性质可知：每加入一个新的A[i]都应该使得总的子序和比单独一个A[i]大才对，否则考虑从A[i]开始寻找新的子段和。当然最终取所有子段和的最大值为最终值。

例子：

待处理数组：-2, 1, -3, 4, -1, 2, 1, -5, 4,

初始化前一个子段和为:0

初始化当前进度下最大子段和为第一个元素的值:-2

前一个子段和为:0

如果加入当前元素-2之后的子段和为:-2

因为加入-2之后整个子段和为-2,不如单独一个当前元素-2大，所以不如从-2开始向后再扩展新的子段和更大

当前新的子段和为:-2

历史最大的子段和为:-2

更新历史最大子段和为:-2

前一个子段和为:-2

如果加入当前元素1之后的子段和为:-1

因为加入1之后整个子段和为-1,不如单独一个当前元素1大，所以不如从1开始向后再扩展新的子段和更大

当前新的子段和为:1

历史最大的子段和为:-2

更新历史最大子段和为:1

前一个子段和为:1

如果加入当前元素-3之后的子段和为:-2

因为加入-3之后整个子段和为-2,比单独一个当前元素-3大，所以扩充-3到上一个子段的尾部

当前新的子段和为:-2

历史最大的子段和为:1

不更新历史最大子段和

前一个子段和为:-2

如果加入当前元素4之后的子段和为:2

因为加入4之后整个子段和为2,不如单独一个当前元素4大，所以不如从4开始向后再扩展新的子段和更大

当前新的子段和为:4

历史最大的子段和为:1

更新历史最大子段和为:4

前一个子段和为:4

如果加入当前元素-1之后的子段和为:3

因为加入-1之后整个子段和为3,比单独一个当前元素-1大，所以扩充-1到上一个子段的尾部

当前新的子段和为:3

历史最大的子段和为:4

不更新历史最大子段和

前一个子段和为:3

如果加入当前元素2之后的子段和为:5

因为加入2之后整个子段和为5,比单独一个当前元素2大，所以扩充2到上一个子段的尾部

当前新的子段和为:5

历史最大的子段和为:4

更新历史最大子段和为:5

前一个子段和为:5

如果加入当前元素1之后的子段和为:6

因为加入1之后整个子段和为6,比单独一个当前元素1大，所以扩充1到上一个子段的尾部

当前新的子段和为:6

历史最大的子段和为:5

更新历史最大子段和为:6

前一个子段和为:6

如果加入当前元素-5之后的子段和为:1

因为加入-5之后整个子段和为1,比单独一个当前元素-5大，所以扩充-5到上一个子段的尾部

当前新的子段和为:1

历史最大的子段和为:6

不更新历史最大子段和

前一个子段和为:1

如果加入当前元素4之后的子段和为:5

因为加入4之后整个子段和为5,比单独一个当前元素4大，所以扩充4到上一个子段的尾部

当前新的子段和为:5

历史最大的子段和为:6

不更新历史最大子段和

最终最大子段和为：6

代码：

复杂度：

时间复杂度：O(nums.length)，遍历一次数组。空间复杂度：O(1)。

积累：

动态规划方法的前提，也就是如何看出来这道题可以使用动态规划。

动态规划求解步骤，最优值、最优解。

其它：

本题还有许多方法，比如：暴力穷举、贪心算法、分治算法等。

回顾一下数据结构知识点课程中讲的哪些算法其实就是用动态规划在求解。

可以尝试求解一下本题最优解。