LeetCode Hot 100：最大子数组
用 current 和 best 讲清最大子数组：每一步决定接上前缀还是重新开始，并给出 JavaScript 实现。
本期讲 LeetCode Hot 100 里的「最大子数组」。原题要求在整数数组
nums 中找出和最大的连续子数组，并返回这个最大和；示例 [-2,1,-3,4,-1,2,1,-5,4] 的答案是 6，对应连续段 [4,-1,2,1]。原题见 LeetCode 53. Maximum Subarray。核心思路：扫描到每个数时，只比较两种选择：从当前数重新开始，或者把当前数接到上一段后面。
current 记录「必须以当前位置结尾」的最大和，best 记录扫描过程中见过的全局最大和。function maxSubArray(nums) {
let current = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}时间复杂度是
O(n)，额外空间复杂度是 O(1)。用 nums[0] 初始化，是为了让全负数组也返回其中最大的那个负数，而不是误判成 0。Related content
- Sign in to comment.