leetcode 53 Maximum Subarray 详细解答
解法1
动态规划：
举例说明：[−2,2,−1,4,−1,2,1,−5,4]
(1)：第一个组合[−2]到以第一个数字结尾的最大连续子数组，则最大值−2(2)：第二个组合[−2,2]到以第二个数字结尾的最大连续子数组，当前最大值2(3)：第三个组合[−2,2,−1]到以第三个数字结尾的最大连续子数组，当前最大值2+(−1)=1(注意，不是2，因为必须要把第三个数字包含在最大子数组中)(4)：第四个组合[−2,2,−1,4]到以第四个数字结尾的最大连续子数组，当前最大值是2+(−1)+4=5(5)：依次类推...
通过上面的观察，得到：
思路是设定一个f(i),这里f(i)表示的就是从下标0,...,i的最大子序列和。那么这里的状态转移方程就是:f(i)=max(f(i−1)+nums[i],nums[i])
最后从每个f(i)选出最大的值，即为要求的结果
代码如下：
由于f(i)只依赖于f(i−1)，所以这里将代码优化为：
时间复杂度：O(N), 空间复杂度：O(1)
