【Hot100|14-LeetCode53. 最大子数组和】

一、问题理解

问题描述

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

示例

text

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

二、核心思路：前缀和 + 最小前缀和追踪

暴力解法的局限性

枚举所有子数组并计算和，时间复杂度为 O(n²)，效率极低。

前缀和优化思路

1. 前缀和定义：prefix[i]表示从数组开头到第i个元素（不包括第i个）的和

2. 核心观察：

   • 子数组nums[i:j]的和 =prefix[j] - prefix[i]

   • 对于每个位置j，要找到prefix[j] - prefix[i]的最大值，就是要找到prefix[i]的最小值（其中i < j）

3. 优化策略：

   • 遍历数组，计算前缀和

   • 同时维护到当前位置的最小前缀和

   • 用当前前缀和减去最小前缀和，得到以当前位置为结尾的最大子数组和

   • 更新全局最大和

三、代码逐行解析

python

from typing import List import math class Solution: def maxSubArray(self, nums: List[int]) -> int: # 1. 初始化 # ans: 存储最大子数组和，初始化为负无穷，确保第一个元素可以更新它 ans = -math.inf # min_pre_sum: 记录到当前位置的最小前缀和，初始为0（空数组的前缀和） min_pre_sum = 0 # pre_sum: 当前前缀和，初始为0 pre_sum = 0 # 2. 遍历数组 for x in nums: # 2.1 更新当前前缀和 pre_sum += x # 2.2 计算以当前位置为结尾的最大子数组和 # 当前前缀和 - 之前的最小前缀和 = 以当前位置为结尾的最大子数组和 ans = max(ans, pre_sum - min_pre_sum) # 2.3 更新最小前缀和 # 注意：先计算ans再更新min_pre_sum，确保min_pre_sum是当前位置之前的最小值 min_pre_sum = min(min_pre_sum, pre_sum) # 3. 返回结果 return ans

四、关键步骤详解

1. 为什么需要min_pre_sum？

对于任意位置j，以j结尾的最大子数组和为：

text

max_sum_ending_at_j = max(prefix[j] - prefix[i]) for all i < j

由于prefix[j]是固定的，要使差值最大，就要使prefix[i]最小。因此，我们只需要维护到当前位置的最小前缀和即可。

2. 为什么min_pre_sum初始化为 0？

• 空数组的前缀和为 0

• 当数组只有一个元素时，最大子数组和就是该元素本身

• 对于第一个元素x：pre_sum = x，ans = max(-∞, x - 0) = x

• 这样处理确保了单个元素的情况也能正确计算

3. 为什么先计算ans再更新min_pre_sum？

我们需要的是当前位置之前的最小前缀和，不包括当前位置。

• 如果先更新min_pre_sum，可能会用到当前前缀和，这会导致计算出的子数组可能为空

• 先计算ans确保min_pre_sum是严格在当前位置之前的最小值

五、算法步骤演示

以nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]为例：

最终结果：6

六、与其他解法的对比

1. 动态规划（Kadane算法）

python

def maxSubArray_kadane(nums): max_sum = nums[0] current_sum = nums[0] for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum

复杂度：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

与本题解法的关系：

• Kadane算法是动态规划的思想：dp[i]表示以i结尾的最大子数组和

• 本题解法是前缀和的思想：最大子数组和 = 当前前缀和 - 最小前缀和

• 两种方法本质相同，都达到了 O(n) 时间复杂度和 O(1) 空间复杂度

2. 分治法

python

def maxSubArray_divide_conquer(nums): def helper(left, right): if left == right: return nums[left] mid = (left + right) // 2 # 左半部分最大子数组和 left_max = helper(left, mid) # 右半部分最大子数组和 right_max = helper(mid + 1, right) # 跨中点的最大子数组和 left_sum = nums[mid] left_temp = nums[mid] for i in range(mid - 1, left - 1, -1): left_temp += nums[i] left_sum = max(left_sum, left_temp) right_sum = nums[mid + 1] right_temp = nums[mid + 1] for i in range(mid + 2, right + 1): right_temp += nums[i] right_sum = max(right_sum, right_temp) cross_max = left_sum + right_sum return max(left_max, right_max, cross_max) return helper(0, len(nums) - 1)

复杂度：

• 时间复杂度：O(n log n)

• 空间复杂度：O(log n)（递归栈空间）

七、复杂度分析

时间复杂度：O(n)

• 只遍历数组一次

• 每次循环执行常数时间操作（加法、减法、比较）

空间复杂度：O(1)

• 只使用了常数个额外变量（ans、min_pre_sum、pre_sum）

八、优化技巧与变体

1. 处理全负数数组

python

def maxSubArray_all_negative(nums): # 如果确定数组全为负数，可以先找到最大值 max_val = max(nums) if max_val < 0: return max_val # 否则使用原算法 ans = -math.inf min_pre_sum = 0 pre_sum = 0 for x in nums: pre_sum += x ans = max(ans, pre_sum - min_pre_sum) min_pre_sum = min(min_pre_sum, pre_sum) return ans

2. 返回最大子数组本身

python

def maxSubArray_with_subarray(nums): ans = -math.inf min_pre_sum = 0 pre_sum = 0 start = 0 end = 0 temp_start = 0 for i, x in enumerate(nums): pre_sum += x if pre_sum - min_pre_sum > ans: ans = pre_sum - min_pre_sum start = temp_start end = i if pre_sum < min_pre_sum: min_pre_sum = pre_sum temp_start = i + 1 return ans, nums[start:end+1] # 示例 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] max_sum, subarray = maxSubArray_with_subarray(nums) print(f"最大和: {max_sum}, 子数组: {subarray}") # 输出: 最大和: 6, 子数组: [4, -1, 2, 1]

3. 处理环形数组（LeetCode 918）

python

def maxSubarraySumCircular(nums): # 环形数组的最大子数组和有两种情况： # 1. 最大子数组在数组中间（非环形） # 2. 最大子数组跨越数组首尾（环形） # 情况2 = 数组总和 - 最小子数组和 total = sum(nums) max_sum = nums[0] min_sum = nums[0] cur_max = nums[0] cur_min = nums[0] for i in range(1, len(nums)): cur_max = max(nums[i], cur_max + nums[i]) max_sum = max(max_sum, cur_max) cur_min = min(nums[i], cur_min + nums[i]) min_sum = min(min_sum, cur_min) # 特殊情况：如果所有数都是负数，则max_sum就是最大负数 if max_sum < 0: return max_sum # 环形情况的最大值 = max(非环形最大和, 总和 - 最小和) return max(max_sum, total - min_sum)

九、常见问题与解答

Q1: 如果数组全为负数，算法还正确吗？

A1: 正确。算法会返回最大的负数。

• 例如nums = [-2, -1]

  • 第一步：pre_sum = -2,ans = -2,min_pre_sum = -2

  • 第二步：pre_sum = -3,ans = max(-2, -3 - (-2)) = -1,min_pre_sum = -3

  • 返回-1，这是正确的（最大子数组是[-1]，和为-1）

Q2: 为什么min_pre_sum初始化为 0 而不是nums[0]？

A2: 初始化为 0 可以正确处理只有一个元素的情况。

• 如果初始化为nums[0]，对于nums = [1]：

  • pre_sum = 1,ans = 1 - 1 = 0，这是错误的

• 初始化为 0：

  • pre_sum = 1,ans = 1 - 0 = 1，这是正确的

Q3: 这个算法和 Kadane 算法哪个更好？

A3: 两者时间复杂度都是 O(n)，空间复杂度都是 O(1)。

• Kadane 算法更直观，直接表达了动态规划的思想

• 前缀和算法更数学化，展示了问题本质

• 在实际应用中，Kadane 算法更常用，但两种方法都是正确的

十、相关题目

1. LeetCode 152. 乘积最大子数组

python

def maxProduct(nums): if not nums: return 0 max_prod = nums[0] min_prod = nums[0] result = nums[0] for i in range(1, len(nums)): # 由于负负得正，需要同时维护最大和最小乘积 temp_max = max(nums[i], max_prod * nums[i], min_prod * nums[i]) temp_min = min(nums[i], max_prod * nums[i], min_prod * nums[i]) max_prod, min_prod = temp_max, temp_min result = max(result, max_prod) return result

2. LeetCode 918. 环形子数组的最大和（前面已提到）

3. LeetCode 121. 买卖股票的最佳时机

python

def maxProfit(prices): if not prices: return 0 min_price = prices[0] max_profit = 0 for price in prices[1:]: # 更新最大利润 max_profit = max(max_profit, price - min_price) # 更新最低价格 min_price = min(min_price, price) return max_profit

十一、总结

核心要点

1. 前缀和是关键：将子数组和问题转化为前缀和之差问题

2. 最小前缀和追踪：对于每个位置，最大子数组和 = 当前前缀和 - 之前的最小前缀和

3. 时间复杂度优化：从暴力解法的 O(n²) 优化到 O(n)

算法步骤

1. 初始化ans为负无穷，min_pre_sum为 0，pre_sum为 0

2. 遍历数组中的每个元素：

   • 更新当前前缀和pre_sum

   • 更新答案ans = max(ans, pre_sum - min_pre_sum)

   • 更新最小前缀和min_pre_sum = min(min_pre_sum, pre_sum)

3. 返回ans

适用场景

• 需要找到连续子数组的最大和

• 数组可能包含负数

• 要求时间复杂度为 O(n)

扩展思考

这个解法展示了如何将看似复杂的问题（最大子数组和）转化为简单的数学关系（前缀和之差），通过追踪最小值来优化计算。这种思想可以应用到许多其他问题中，如：

• 最小子数组和

• 子数组和接近某个目标值

• 二维数组的最大子矩阵和

掌握前缀和+最小前缀和追踪的解法，不仅能够解决最大子数组和问题，还能够解决一系列类似的子数组和问题，是面试中非常重要的算法技巧。