LeetCode | 53. 最大子序和

[aermin]

题目

解法

动态规划

思路及代码

问题是在求解0 ~ n-1中，找出值为最大的f(i)，f(i)是各种可能为答案的状态(各种连续子数组之和)

那么，只要用数组来保存 f(i)的值，然后遍历取最大值即可

f(i)值怎么求？我们可以考虑单独成为一段还是加入 f(i - 1) 对应的那一段，这取决于 ai
和 f(i - 1) + ai 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

比如这个：
[-1 3 -2 4 -2 -2 5]

-1 时最大值为-1，连续子数组为[-1]
-1 3 时最大值为3，连续子数组为[3]
3 -2 时最大值为3, 连续子数组为[3]
3 -2 4 时最大值为5, 连续子数组为[3,-2,4]
3 -2 4 -2 时最大值为5, 连续子数组为[3,-2,4]
3 -2 4 -2 5 时最大值为8，连续子数组为[3,-2,4,-2,5]

把每次得到当前最大值存起来，当前最大值 与 下一个数相加f(i-1) +ai， 结果与ai相比，如果两者有值比当前最大值大，则更新当前最大值，否则继续与下一个数(ai+1)相加和对比。

换句话说，存起当前最大值f(i-x)，当遇到有比当前最大值还大的temp值f(i-1) +ai或者最新数ai，就去更新当前最大值f(i-x)

/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
// 动态转移方程：f(i)=max{f(i−1)+ai,ai}
// 声明一个temp变量来遍历nums求f(i),初始值为0；
// 声明一个maxAns变量来比较本次f(i),初始值为nums[0]。
// 比较temp和maxAns(之前最大值)的大小，大的赋值给maxAns
var maxSubArray = function(nums) {
   let temp = 0, maxAns = nums[0], numsLength = nums.length;
   for(let i = 0; i < numsLength; i++) {
        temp = Math.max(temp + nums[i], nums[i]);
        maxAns = Math.max(temp, maxAns);
   }
   return maxAns;
};

复杂度分析

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。

图解

Reference

题解