53. 最大子数组和 Medium

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

解题思路

输入：一个数组 nums

输出：找出一个具有最大和的连续子数组，返回其最大和

本题属于 动态规划 问题。

最经典解法是 Kadane 算法：一次遍历，维护“以当前元素结尾的最大子数组和”，并同步刷新全局最大值。

状态定义：

• curr：以当前位置结尾的最大和（要么把自己并入之前的和，要么从自己重新开始）。
• best：全局最大和。

关键点/易错点:

• 当数组全为负数时，答案是“最大的那个负数”；初始化为 nums[0] 能自然覆盖。
• 不要把 curr 初始化为 0（会错误忽略全负数组）。

代码实现

python

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # curr: 以当前元素结尾的最大子数组和
        # best: 全局最大子数组和
        curr = best = nums[0]
        for x in nums[1:]:
            # 要么把当前元素接在之前的最大和后面，要么从当前元素重新开始
            curr = max(x, curr + x)
            best = max(best, curr)
        return best

javascript

var maxSubArray = function(nums) {
    let curr = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(curr, best);
    }

    return best;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

53 国际版

53 中文版