LeetCode 53. 最大子数组和

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（Kadane 算法）（推荐）
相似题目

题目描述

✅ 53. 最大子数组和

题目：

给定一个整数数组 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
解释：整个数组即为最优子数组，和为 23。

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：

已实现 O(n) 解法后，可尝试用分治法求解。

思路分析

解法一：动态规划（Kadane 算法）（推荐）

核心思路：

定义 cur 为以当前位置结尾的最大子数组和。

若 cur < 0 则抛弃前缀，从当前元素重新开始；否则继续累加。

每步更新全局最大值 res。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外变量。

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 若前缀和为负则从当前位置重新开始
            cur = Math.max(nums[i], cur + nums[i]);
            res = Math.max(res, cur);
        }

        return res;
    }
}

func maxSubArray(nums []int) int {
	cur := nums[0]
	res := nums[0]

	for i := 1; i < len(nums); i++ {
		// 若前缀和为负则从当前位置重新开始
		if cur < 0 {
			cur = nums[i]
		} else {
			cur += nums[i]
		}
		if cur > res {
			res = cur
		}
	}

	return res
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	动态规划
152. 乘积最大子数组	中等	动态规划
697. 数组的度	简单	哈希表
978. 最长湍流子数组	中等	动态规划、滑动窗口
1749. 任意子数组和的绝对值的最大值	中等	动态规划
2321. 拼接数组的最大分数	困难	动态规划
2272. 最大波动的子字符串	困难	动态规划
2302. 统计得分小于 K 的子数组数目	困难	滑动窗口
2496. 数组中字符串的最大值	简单	字符串处理
2600. K 件物品的最大和	简单	贪心
2606. 找到最大开销的子字符串	中等	动态规划
2609. 最长平衡子字符串	简单	字符串
3026. 最大好子数组和	中等	哈希表、动态规划
3318. 计算子数组的 x 值 II	困难	动态规划
918. 环形子数组的最大和	中等	动态规划
560. 和为 K 的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/31655177