教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕「算法通关手册」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 ansMaxsubMax承担原dp[i]的角色ansMax承担原max(dp)的角色二者在遍历中同步更新语义与思路一完全一致。思路二复杂度分析时间复杂度$O(n)$其中 $n$ 为数组nums的元素个数。空间复杂度$O(1)$仅使用两个额外变量。五、思路三分治算法分治是一种「拆分—求解—合并」的通用思维范式参见仓库的分治算法章节。本题同样可以用分治优雅求解并且该解法被仓库的分治章节列为练习题目。核心思想三种情况的划分将数组nums根据中心位置分为左右两个子数组则具有最大和的连续子数组只可能属于以下 $3$ 种情况最大和子数组完全在左子数组中最大和子数组完全在右子数组中最大和子数组跨过中心位置一部分在左子数组中另一部分在右子数组中。分别求解这三种情况再取最大值即可得到当前数组的最大子数组和。具体步骤将数组nums根据中心位置递归分为左右两个子数组直到所有子数组长度为 $1$。长度为 $1$ 的子数组最大和就是数组中唯一的那个数直接返回递归基。递归求出左子数组的最大和leftMax。递归求出右子数组的最大和rightMax。求出跨过中心位置的子数组最大和leftTotal rightTotal从中心向左扩展累加求左侧最大后缀和从中心向右扩展累加求右侧最大前缀和两者相加即为跨越中心的子数组最大和。取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[mid1]因此从中心分别向左右两侧扩展累加并记录过程中的最大值。分治递归需要明确且正确的递归基与边界避免无穷递归与越界这是仓库分治章节强调的实践要点。思路三复杂度分析时间复杂度$O(n)$。虽然递归划分本身是 $O(\log n)$ 层但每一层对跨越中心的左右扩展需要扫描当前区间内的元素整体呈线性累计因此总时间复杂度为 $O(n)$而非 $O(n \log n)$。空间复杂度$O(\log n)$来自递归调用栈的深度。六、三种思路对比与选型建议解法时间复杂度空间复杂度适用场景思路一一维 DP$O(n)$$O(n)$便于理解状态定义与转移过程适合教学与推导思路二DP 滚动优化Kadane$O(n)$$O(1)$实际刷题与面试的首选代码最精简思路三分治$O(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 题清单可见其面试高频属性。八、进阶延伸仓库中的系列相关题目掌握了本题的状态设计与滚动优化套路后可以在仓库中继续攻克一系列变式题形成完整的「最大子数组」知识网络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])同样可以做滚动优化。0918. 环形子数组的最大和数组首尾相连成环。将答案拆成「普通区间最大和」与「sum(nums) - 最小子数组和」两种情况取较大值其中普通最大子数组和问题与本题完全一致。1186. 删除一次得到子数组最大和允许至多删除一个元素需要引入「是否已删除」这一额外维度扩展状态。1191. K 次串联后最大子数组之和将数组重复 K 次后求最大子数组和需要结合拼接特性分类讨论。这四道题及其题解索引见 docs/solutions/1100-1199/index.md从「单数组」延伸到「乘积」「环形」「可删除」「多段拼接」是检验对 Kadane 类问题理解深度的最佳练习序列。总结LeetCode 0053 最大子数组和虽然只有「中等」难度却同时覆盖了数组、动态规划、分治三类核心考点。以「结尾位置」定义状态的思路一是所有解法的基础滚动优化到两个变量的思路二Kadane 算法是工程与面试中最常用的形态思路三则展示了分治「拆分—求解—合并」范式在区间问题上的应用。掌握本题等于同时拿到线性 DP 与分治两类题型的入门钥匙仓库中以上所列章节与系列题目可供进一步巩固。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐VLC视频转码终极指南如何免费将任何视频转换为理想格式VLC视频转码终极指南如何免费将任何视频转换为理想格式 VLC媒体播放器不仅是全球最受欢迎的多媒体播放器更是一个功能强大的视频转码工具。这款开源软件能让你免教程文档知识库AlgoNote 算法通关手册LeetCode 0087 扰乱字符串Scramble String三维动态规划详解AlgoNote 算法通关手册LeetCode 0087 扰乱字符串Scramble String三维动态规划详解 导读 本文是 AlgoNote「算法通教程文档知识库AlgoNote 算法通关手册LeetCode 0055 跳跃游戏Jump Game贪心与动态规划全解AlgoNote 算法通关手册LeetCode 0055 跳跃游戏Jump Game贪心与动态规划全解 导读 本文基于「算法通关手册」AlgoNote 仓教程文档知识库上一篇如何构建交互式图数据可视化界面下一篇TRL完整教程从零开始掌握AI模型微调的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考