LeetCode #53：最大子数组和
1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 面试算法LeetCodeLeetCode-MediumTS/JSPython动态规划子数组问题Kadane
题干
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例
输入：
nums = [-2,1,-3,4,-1,2,1,-5,4]输出：
6
输入：
nums = [1]输出：
1
输入：
nums = [5,4,-1,7,8]输出：
23
题目分析
最典型的动态规划中的子数组问题，淘天面试题也出过，用 Kadane 算法就能解决。具体的解释可以看上面的链接，这里直接给出题解。
题解：Kadane 算法
ts
function maxSubArray(nums: number[]): number {
let curr_max = nums[0];
let glob_max = nums[0];
nums.slice(1).forEach(el => {
curr_max = Math.max(el, curr_max + el);
glob_max = Math.max(glob_max, curr_max);
});
return glob_max;
}python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
curr_max = nums[0]
glob_max = nums[0]
for i in range(1, len(nums)):
curr_max = max(nums[i], curr_max + nums[i])
glob_max = max(glob_max, curr_max)
return glob_max