剑指Offer 42 - 连续子数组的最大和
2021-04-30 16:27
标签：思路 剑指offer margin 单元 var 规划 记录 leetcode 也有 力扣链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/ 题目描述 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 思路：动态规划 递推公式： 以第n个数结尾的和最大的数组最大值一定在以下两个数组中产生： 假设我们已知以第n-1个数结尾的所有子数组中，总和的最大值为F(n-1)。 则有 F(n) = max( arr[n] , F(n-1)+arr[n] ) 初始化： F(0) = arr[0] 结束条件： n === arr.length-1 (参与最后一次迭代) 迭代过程中，使用一个maxSum变量记录当前最大的子数组和。 代码： 时间复杂度：O(N) 空间复杂度：O(1) 剑指Offer 42 - 连续子数组的最大和 标签：思路 剑指offer margin 单元 var 规划 记录 leetcode 也有 原文地址：https://www.cnblogs.com/xintangchn/p/13227812.html
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
const len = nums.length;
if(!len) return 0;
let curMax = nums[0];
let maxSum = nums[0];
for(let i = 1; i ){
curMax = Math.max(curMax + nums[i], nums[i]);
if(curMax > maxSum){
maxSum = curMax;
}
}
return maxSum;
};