求一个数组的最大连续子数组和
时间复杂度O(n)
空间复杂度O(1)
动态规划方法求解：递推公式为DP[i] = DP[i-1] + arr[i], faster than 84%
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var max = nums[0]
var cur = 0
for(var i = 0; i < nums.length; i++){
cur += nums[i]
if(cur < 0 || nums[i] > cur) cur = nums[i]
max = Math.max(cur, max)
}
return max
};
更方便理解的递推
- Runtime: 88 ms, faster than 50.81%
- Memory Usage: 37.4 MB, less than 49.28%
var maxSubArray = function(nums) {
let len = nums.length
let cur = 0
let max = nums[0]
for(let i = 0; i < len; i++) {
cur = Math.max(cur + nums[i], nums[i])
max = Math.max(cur, max)
}
return max
};
