企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文围绕「算法通关手册」AlgoNote 仓库中的经典题解 0053. 最大子数组和 展开，系统讲解这道数组、分治、动态规划三重标签的「中等」题。读完本文，你将掌握一维线性动态规划的「以结尾位置定义状态」套路、空间复杂度从 $O(n)$ 降到 $O(1)$ 的滚动优化（即经典的 Kadane 算法），以及基于「拆分—求解—合并」范式实现的分治解法，并能在仓库中定位到对应章节与系列进阶题目，直接用于面试刷题复习。

一、题目速览

题目名称：0053. 最大子数组和（Maximum Subarray）

• 标签：数组、分治、动态规划
• 难度：中等
• 所属章节：0001-0099 题解索引（第 0053 题）

题目描述：给定一个整数数组nums，要求找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

题目说明：

• 子数组：指的是数组中的一个连续部分。
• 约束条件：$1 \le nums.length \le 10^5$，$-10^4 \le nums[i] \le 10^4$。

示例：

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

从约束可以看出，数组长度最大可达 $10^5$，因此 $O(n^2)$ 的暴力枚举所有子数组是无法接受的，必须设计 $O(n)$ 或 $O(n \log n)$ 级别的算法。

二、前置概念：子数组与子序列的区别

在动手解题前，先厘清两个容易混淆的概念（仓库的线性 DP 章节对此有明确说明）：

• 子数组：原数组中一段连续的元素组成的序列。
• 子序列：从原数组中按顺序选取若干元素（可以不连续），只要不改变元素的相对顺序即可。

两者都保持元素原有顺序，区别在于子数组要求元素连续，子序列不要求连续。本题要求的正是「连续子数组」，因此「以某个位置结尾的一段连续区间」是天然的状态划分依据，这正是一维线性 DP 的标准切入点。

三、思路一：动态规划（一维线性 DP，标准解法）

1. 阶段划分

按照连续子数组的结束位置进行阶段划分，即每一阶段对应「以第 $i$ 个元素结尾」的子数组。

2. 定义状态

定义状态 $dp[i]$ 为：以第 $i$ 个数结尾的连续子数组的最大和。

这里的关键在于：状态必须包含「结尾位置」这一信息。以第 $i$ 个数结尾的子数组只有两种构成方式——要么单独由nums[i]构成，要么由「以 $i-1$ 结尾的某个子数组」再接上nums[i]，因此状态天然满足无后效性。

3. 状态转移方程

从「以第 $i-1$ 个数结尾的连续子数组的最大和」以及「第 $i$ 个数的值」出发讨论 $dp[i]$：

• 如果 $dp[i-1] < 0$，则「以第 $i-1$ 个数结尾的子数组最大和」加上「第 $i$ 个数的值」会小于「第 $i$ 个数的值」，即 $dp[i-1] + nums[i] < nums[i]$。说明前面的子数组对当前元素是负贡献，此时不如从当前元素重新开始，取 $dp[i] = nums[i]$。
• 如果 $dp[i-1] \ge 0$，则「以第 $i-1$ 个数结尾的子数组最大和」加上「第 $i$ 个数的值」不小于「第 $i$ 个数的值」，即 $dp[i-1] + nums[i] \ge nums[i]$。说明前面的子数组对当前元素是正贡献，可以继续累加，取 $dp[i] = dp[i-1] + nums[i]$。

归纳得到状态转移方程：

$$dp[i] = \begin{cases} nums[i], & dp[i - 1] < 0 \ dp[i - 1] + nums[i], & dp[i - 1] \ge 0 \end{cases}$$

4. 初始条件

以第 $0$ 个数结尾的连续子数组最大和就是nums[0]本身，即 $dp[0] = nums[0]$。

5. 最终结果

根据状态定义，$dp[i]$ 是以第 $i$ 个数结尾的子数组最大和，而题目要求的最大和子数组可以在任意位置结束，因此最终答案是所有 $dp[i]$ 中的最大值，即 $max(dp)$。

思路一：完整代码

class Solution: def maxSubArray(self, nums: List[int]) -> int: size = len(nums) dp = [0 for _ in range(size)] dp[0] = nums[0] for i in range(1, size): if dp[i - 1] < 0: dp[i] = nums[i] else: dp[i] = dp[i - 1] + nums[i] return max(dp)

思路一：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为数组nums的元素个数，只需一趟线性扫描。
• 空间复杂度：$O(n)$，需要长度为 $n$ 的dp数组。

补充说明：转移方程写成dp[i] = max(nums[i], dp[i-1] + nums[i])与上述if/else形式完全等价，这也是许多题解采用的紧凑写法。

四、思路二：动态规划 + 滚动优化（Kadane 算法）

优化动机

观察状态转移方程可以发现，$dp[i]$只依赖$dp[i-1]$ 与当前元素 $nums[i]$，并不需要回头看更早的状态。因此完全没有必要保留整个dp数组，可以用一个变量subMax表示「以第 $i$ 个数结尾的连续子数组的最大和」，再用另一个变量ansMax保存全局最大值。这就是空间复杂度从 $O(n)$ 降到 $O(1)$ 的滚动优化，也是著名的Kadane 算法的核心形态。

思路二：完整代码

class Solution: def maxSubArray(self, nums: List[int]) -> int: size = len(nums) subMax = nums[0] ansMax = nums[0] for i in range(1, size): if subMax < 0: subMax = nums[i] else: subMax += nums[i] ansMax = max(ansMax, subMax) return ansMax

subMax承担原dp[i]的角色，ansMax承担原max(dp)的角色，二者在遍历中同步更新，语义与思路一完全一致。

思路二：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为数组nums的元素个数。
• 空间复杂度：$O(1)$，仅使用两个额外变量。

五、思路三：分治算法

分治是一种「拆分—求解—合并」的通用思维范式（参见仓库的分治算法章节）。本题同样可以用分治优雅求解，并且该解法被仓库的分治章节列为练习题目。

核心思想：三种情况的划分

将数组nums根据中心位置分为左右两个子数组，则具有最大和的连续子数组只可能属于以下 $3$ 种情况：

1. 最大和子数组完全在左子数组中；
2. 最大和子数组完全在右子数组中；
3. 最大和子数组跨过中心位置，一部分在左子数组中，另一部分在右子数组中。

分别求解这三种情况再取最大值，即可得到当前数组的最大子数组和。

具体步骤

1. 将数组nums根据中心位置递归分为左右两个子数组，直到所有子数组长度为 $1$。
2. 长度为 $1$ 的子数组最大和就是数组中唯一的那个数，直接返回（递归基）。
3. 递归求出左子数组的最大和leftMax。
4. 递归求出右子数组的最大和rightMax。
5. 求出跨过中心位置的子数组最大和leftTotal + rightTotal：从中心向左扩展累加求左侧最大后缀和，从中心向右扩展累加求右侧最大前缀和，两者相加即为跨越中心的子数组最大和。
6. 取leftMax、rightMax、leftTotal + rightTotal三者的最大值返回。

思路三：完整代码

class Solution: def maxSubArray(self, nums: List[int]) -> int: def max_sub_array(low, high): if low == high: return nums[low] mid = low + (high - low) // 2 leftMax = max_sub_array(low, mid) rightMax = max_sub_array(mid + 1, high) total = 0 leftTotal = -inf for i in range(mid, low - 1, -1): total += nums[i] leftTotal = max(leftTotal, total) total = 0 rightTotal = -inf for i in range(mid + 1, high + 1): total += nums[i] rightTotal = max(rightTotal, total) return max(leftMax, rightMax, leftTotal + rightTotal) return max_sub_array(0, len(nums) - 1)

代码细节说明：

• 递归基为low == high，此时子数组只有一个元素，直接返回nums[low]。
• 跨越中心的最大和必须强制包含nums[mid]与nums[mid+1]，因此从中心分别向左右两侧扩展累加并记录过程中的最大值。
• 分治递归需要明确且正确的递归基与边界，避免无穷递归与越界，这是仓库分治章节强调的实践要点。

思路三：复杂度分析

• 时间复杂度：$O(n)$。虽然递归划分本身是 $O(\log n)$ 层，但每一层对跨越中心的左右扩展需要扫描当前区间内的元素，整体呈线性累计，因此总时间复杂度为 $O(n)$，而非 $O(n \log n)$。
• 空间复杂度：$O(\log n)$，来自递归调用栈的深度。

六、三种思路对比与选型建议

面试中推荐优先掌握思路二（Kadane 算法），同时能讲清楚思路一的推导过程（阶段划分、状态定义、转移方程、初始条件、最终结果五步法），分治则常作为「你能用分治再做一遍吗」的追问出现。

七、仓库定位：本解法在「算法通关手册」中的位置

本题在仓库中处于核心枢纽位置，出现在多份导航与索引文档中：

• 题解本体：docs/solutions/0001-0099/maximum-subarray.md，本文内容即源于此。
• 线性 DP 章节经典例题：docs/08_dynamic_programming/08_03_linear_dp_01.md 第 3.2 节将本题作为「子数组相关线性 DP」的入门例题，并详细区分了子数组与子序列。
• 分治章节练习题目：docs/07_algorithm/07_03_divide_and_conquer_algorithm.md 将本题列为分治算法练习。
• 题解总索引：docs/solutions/0001-0099/index.md 收录本题。
• 分类与面试清单：本题出现在题目分类列表的「数组」「分治」「动态规划」多个分类下，同时被收录进面试 100 题清单与面试 200 题清单，可见其面试高频属性。

八、进阶延伸：仓库中的系列相关题目

掌握了本题的状态设计与滚动优化套路后，可以在仓库中继续攻克一系列变式题，形成完整的「最大子数组」知识网络：

1. 0152. 乘积最大子数组：把「求和」换成「求乘积」。由于负数乘负数得正数，需要同时维护以 $i$ 结尾的最大值与最小值两个状态（dp_max[i]与dp_min[i]），转移方程为dp_max[i] = max(dp_max[i-1] * nums[i], nums[i], dp_min[i-1] * nums[i])，同样可以做滚动优化。
2. 0918. 环形子数组的最大和：数组首尾相连成环。将答案拆成「普通区间最大和」与「sum(nums) - 最小子数组和」两种情况取较大值，其中普通最大子数组和问题与本题完全一致。
3. 1186. 删除一次得到子数组最大和：允许至多删除一个元素，需要引入「是否已删除」这一额外维度扩展状态。
4. 1191. K 次串联后最大子数组之和：将数组重复 K 次后求最大子数组和，需要结合拼接特性分类讨论。

这四道题（及其题解索引见 docs/solutions/1100-1199/index.md）从「单数组」延伸到「乘积」「环形」「可删除」「多段拼接」，是检验对 Kadane 类问题理解深度的最佳练习序列。

总结

LeetCode 0053 最大子数组和虽然只有「中等」难度，却同时覆盖了数组、动态规划、分治三类核心考点。以「结尾位置」定义状态的思路一是所有解法的基础；滚动优化到两个变量的思路二（Kadane 算法）是工程与面试中最常用的形态；思路三则展示了分治「拆分—求解—合并」范式在区间问题上的应用。掌握本题，等于同时拿到线性 DP 与分治两类题型的入门钥匙，仓库中以上所列章节与系列题目可供进一步巩固。

• 教程
• 文档
• 知识库