您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode中如何找到最大子序和
## 目录
1. [问题描述](#问题描述)
2. [暴力解法](#暴力解法)
3. [动态规划解法](#动态规划解法)
4. [分治法](#分治法)
5. [Kadane算法](#kadane算法)
6. [代码实现与复杂度分析](#代码实现与复杂度分析)
7. [总结](#总结)
## 问题描述
LeetCode第53题"最大子序和"（Maximum Subarray）要求：给定一个整数数组`nums`，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：
```python
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为6。
通过双重循环枚举所有可能的子数组，计算每个子数组的和并记录最大值。
def maxSubArray(nums):
max_sum = float('-inf')
n = len(nums)
for i in range(n):
current_sum = 0
for j in range(i, n):
current_sum += nums[j]
max_sum = max(max_sum, current_sum)
return max_sum
该方法在LeetCode提交会超时，仅适用于小规模数据。
定义dp[i]表示以nums[i]结尾的最大子序和，状态转移方程为：
dp[i] = max(nums[i], dp[i-1] + nums[i])
def maxSubArray(nums):
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)
观察到dp[i]只与dp[i-1]相关，可以用单个变量替代数组：
def maxSubArray(nums):
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
max_global = max(max_global, max_current)
return max_global
def maxSubArray(nums):
def helper(l, r):
if l == r:
return nums[l]
mid = (l + r) // 2
left_max = helper(l, mid)
right_max = helper(mid+1, r)
# 计算跨越中点的最大和
left_sum = right_sum = float('-inf')
current = 0
for i in range(mid, l-1, -1):
current += nums[i]
left_sum = max(left_sum, current)
current = 0
for i in range(mid+1, r+1):
current += nums[i]
right_sum = max(right_sum, current)
return max(left_max, right_max, left_sum + right_sum)
return helper(0, len(nums)-1)
动态规划的优化版本，维护两个变量：
- max_current：当前子数组的最大和
- max_global：全局最大和
def maxSubArray(nums):
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
max_global = max(max_global, max_current)
return max_global
当数组全为负数时，算法依然有效：
输入：nums = [-2,-1,-3]
输出：-1
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(n²) | O(1) | 仅用于理解问题 |
| 动态规划 | O(n) | O(n)/O(1) | 标准解法 |
| 分治法 | O(n log n) | O(log n) | 学术研究 |
| Kadane算法 | O(n) | O(1) | 最优解，推荐使用 |
提示：LeetCode官方题解通常包含多种语言实现，建议对比学习不同语言的写法差异。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。