最大子数组和（Maximum Subarray）七种解法全解析：基于 leetcode 仓库的 Kadane 算法、动态规划与分治实战指南

最大子数组和Maximum Subarray七种解法全解析基于 leetcode 仓库的 Kadane 算法、动态规划与分治实战指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 Maximum Subarray最大子数组和 为核心系统讲解 LeetCode 53 号题的七种解法——从 O(n²) 暴力枚举、递归与记忆化到 O(n) 的自顶向下 / 自底向上动态规划、空间优化 DP、Kadane 算法再到 O(n log n) 分治法。文章同时结合本仓库leetcode中 12 种语言的 0053 号题实现给出可直接复制运行的完整代码与源码级佐证。读完本文你将理解最大子数组和这一经典 DP 问题的完整解题脉络掌握 Kadane 算法及其等价变体并能识别该题最常见的两类实现陷阱。问题定义与前置知识问题描述给定一个整数数组nums找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。例如nums [-2,1,-3,4,-1,2,1,-5,4]时最大子数组为[4,-1,2,1]最大和为6该示例同时记录在 cpp/0053-maximum-subarray.cpp 的注释中。在开始求解之前原文档要求读者熟悉以下四项前置知识Kadane 算法—— 最大子数组问题的经典 O(n) 动态规划解法动态规划—— 理解如何从子问题构建答案自顶向下与自底向上两种思路分治法—— 将数组拆分、并处理跨边界子数组的替代方案递归 记忆化—— 将递归解转换为高效 DP 解的通用技巧。本仓库的 hints/maximum-subarray.md 进一步给出了官方建议的复杂度目标O(n) 时间、O(1) 空间其中n为输入数组长度。这也是为什么我们最终要把目光落在 Kadane 算法上。1. 暴力枚举Brute ForceO(n²) 的直观起点直觉本题要求的是任意连续子数组的最大和。最直接的思路是尝试每一个可能的子数组计算其和持续记录所见过的最大的和。一个子数组由起始下标i和结束下标j唯一确定。固定i并向右扩展j即可算出所有以i开头的子数组之和。这种方法易于理解、适合学习但对于大规模输入并不高效。算法步骤设n为数组长度用数组第一个元素初始化结果res遍历所有可能的起始下标i从0到n - 1对每个i初始化累加和cur 0遍历结束下标j从i到n - 1将nums[j]累加进cur用res与cur的较大值更新res所有子数组检查完毕后返回res。代码实现class Solution: def maxSubArray(self, nums: List[int]) - int: n, res len(nums), nums[0] for i in range(n): cur 0 for j in range(i, n): cur nums[j] res max(res, cur) return res说明本文各解法均以 Python 给出完整可运行实现原文档同时提供了 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 等语言版本仓库中对应文件可参考下文仓库实战实现速览一节。复杂度分析时间复杂度$O(n ^ 2)$空间复杂度$O(1)$2. 递归Recursion用状态机理解子数组直觉借助递归可以把问题看成在每个下标处做一次决策要么尚未开始一个子数组要么已经身处某个子数组内部可以决定继续它或终止它。递归函数用一个布尔标志flag记录当前状态flag False—— 尚未开始任何子数组flag True—— 正在构建子数组。函数回答的问题是给定当前是否已处于子数组内部从下标i出发能得到的最大子数组和是多少通过在每个位置探索两种可能性递归最终能找到最优的连续子数组。算法步骤定义递归函数dfs(i, flag)i为当前数组下标flag表示子数组是否已经开始。基本情况若i是最后一个下标若子数组已开始可以选择在该元素前终止或包含它取max(0, nums[i])若子数组尚未开始则必须选择该元素。若flag为True处于子数组内部两种选择终止子数组返回0或累加nums[i]后继续递归取二者较大值。若flag为False尚未开始可以跳过当前元素保持未开始状态也可以从当前元素开启新子数组取二者较大值。以dfs(0, False)启动递归返回最终结果。代码实现class Solution: def maxSubArray(self, nums: List[int]) - int: def dfs(i, flag): if i len(nums) - 1: return max(0, nums[i]) if flag else nums[i] if flag: return max(0, nums[i] dfs(i 1, True)) return max(dfs(i 1, False), nums[i] dfs(i 1, True)) return dfs(0, False)复杂度分析时间复杂度$O(2 ^ n)$每个状态都有两个分支指数级空间复杂度$O(n)$递归调用栈深度3. 动态规划自顶向下 / 记忆化O(n) 的第一次飞跃直觉递归解法虽然思路清晰但纯递归会反复计算相同的子问题。为消除重复计算我们引入自顶向下动态规划记忆化。每个状态由二元组唯一标识i当前数组下标flag子数组是否已开始True/False。函数回答给定子数组是否已经在进行中从下标i出发能得到的最大子数组和是多少通过为每个(i, flag)状态缓存结果避免重复计算时间复杂度从指数级降为线性。算法步骤创建记忆表memo其中memo[i][flag]存储在给定flag状态下、从下标i出发的最大子数组和定义递归函数dfs(i, flag)含义同上基本情况i为最后一个下标时按是否已在子数组内返回max(0, nums[i])或nums[i]若(i, flag)的结果已在memo中直接返回若flag为True取终止子数组0与累加nums[i]继续二者的较大值存入memo若flag为False取跳过当前元素与从当前元素开启新子数组二者的较大值存入memo以dfs(0, False)启动返回结果。代码实现class Solution: def maxSubArray(self, nums: List[int]) - int: memo [[None] * 2 for _ in range(len(nums))] def dfs(i, flag): if i len(nums) - 1: return max(0, nums[i]) if flag else nums[i] if memo[i][flag] is not None: return memo[i][flag] if flag: memo[i][flag] max(0, nums[i] dfs(i 1, True)) else: memo[i][flag] max(dfs(i 1, False), nums[i] dfs(i 1, True)) return memo[i][flag] return dfs(0, False)复杂度分析时间复杂度$O(n)$每个(i, flag)状态只计算一次空间复杂度$O(n)$记忆表 递归栈4. 动态规划自底向上从右往左填表直觉从递归与自顶向下解法中我们提炼出两个有用的状态恰好从下标i开始的最佳子数组和从下标i或之后开始的最佳子数组和。不使用递归我们可以在自底向上动态规划中迭代计算这两个值。在每个下标处决定是否从当前元素开启新子数组还是从下一个下标延伸已有子数组。由于 DP 表从右往左填充所有需要的未来值在计算当前值时都已知。算法步骤设n为数组长度创建大小为n x 2的 DP 表dpdp[i][1]必须从下标i开始的最大子数组和dp[i][0]从下标i或更靠后开始的最大子数组和初始化最后下标的基础情况dp[n - 1][1] nums[n - 1]dp[n - 1][0] nums[n - 1]令i从n - 2递减到0计算dp[i][1]取从i开启新子数组nums[i]与延伸i 1的子数组nums[i] dp[i 1][1]的较大值计算dp[i][0]取最佳子数组在更靠后处开始dp[i 1][0]与恰好在i开始dp[i][1]的较大值填表完成后dp[0][0]即最大子数组和返回dp[0][0]。代码实现class Solution: def maxSubArray(self, nums: List[int]) - int: n len(nums) dp [[0] * 2 for _ in range(n)] dp[n - 1][1] dp[n - 1][0] nums[n - 1] for i in range(n - 2, -1, -1): dp[i][1] max(nums[i], nums[i] dp[i 1][1]) dp[i][0] max(dp[i 1][0], dp[i][1]) return dp[0][0]复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$5. 动态规划空间优化版以i结尾的最大子数组和直觉在每个位置我们面对一个简单选择从当前元素开启新子数组或延伸前一个下标结束的子数组。若到前一个下标为止的累加和为负延伸它只会让结果更糟因此应在当前元素处重新开始。这个思想让我们只需维护以每个下标结尾的最佳子数组和一趟扫描即可完成更新。算法步骤创建数组dp其中dp[i]表示以下标i结尾的最大子数组和将dp初始化为nums的拷贝——因为以每个下标结尾的最小子数组就是元素本身从下标1遍历到末尾更新dp[i]为从nums[i]重新开始或延伸前一子数组nums[i] dp[i - 1]二者取较大值最大子数组和即dp中的最大值返回该值。代码实现class Solution: def maxSubArray(self, nums): dp [*nums] for i in range(1, len(nums)): dp[i] max(nums[i], nums[i] dp[i - 1]) return max(dp)复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$从该版本出发只需用两个变量分别保存前一位置的dp[i-1]与全局最大值即可把空间压缩到 O(1)——这正是下一节 Kadane 算法的本质。6. Kadane 算法O(n) 时间、O(1) 空间的终极形态直觉Kadane 算法基于一个简单观察一旦累加和变为负数保留它只会拖累未来任何子数组的和。因此每当当前和降到零以下就重置它从下一个元素开启新子数组。单趟扫描数组时同时维护以当前位置结尾的最佳子数组和全局见过的最大子数组和。算法步骤初始化curSum 0追踪当前子数组累加和maxSub取第一个元素以正确处理全负数组。遍历数组中的每个数若curSum为负将其重置为0开启新子数组将当前数累加进curSum用maxSub与curSum的较大值更新maxSub。处理完所有元素后返回maxSub。代码实现Pythonclass Solution: def maxSubArray(self, nums: List[int]) - int: maxSub, curSum nums[0], 0 for num in nums: if curSum 0: curSum 0 curSum num maxSub max(maxSub, curSum) return maxSub复杂度分析时间复杂度$O(n)$空间复杂度$O(1)$仓库源码印证Kadane 的两种等价写法在leetcode仓库中0053 号题的实现全部采用 Kadane 思路但存在两种等价变体值得对比学习变体 A先累加、后重置与上文算法步骤一致python/0053-maximum-subarray.pyclass Solution: def maxSubArray(self, nums: List[int]) - int: res nums[0] total 0 for n in nums: total n res max(res, total) if total 0: total 0 return resgo/0053-maximum-subarray.go、rust/0053-maximum-subarray.rs、c/0053-maximum-subarray.c、typescript/0053-maximum-subarray.ts、ruby/0053-maximum-subarray.rb 均采用相同模式java/0053-maximum-subarray.java 则用Integer.MIN_VALUE初始化max同样安全处理了全负数组。变体 Bcur max(cur nums[i], nums[i])一步内完成继续或重启决策cpp/0053-maximum-subarray.cppclass Solution { public: int maxSubArray(vectorint nums) { int curr nums[0]; int result nums[0]; for (int i 1; i nums.size(); i) { curr max(curr nums[i], nums[i]); result max(result, curr); } return result; } };kotlin/0053-maximum-subarray.kt 的maxOf(currsum num, num)与之完全等价。两种写法在数学上等价max(cur x, x) x max(cur, 0)即若此前累加和为负则重置为 0。仓库同时提供了 javascript/0053-maximum-subarray.js、csharp/0053-maximum-subarray.cs、swift/0053-maximum-subarray.swift 等其余语言版本均可直接对照阅读。7. 分治法Divide Conquer直觉分治法将数组一分为二并递归求解。对于任意区间[l .. r]最大子数组必然是以下三种情况之一完全位于左半区完全位于右半区跨越中点包含中间元素。前两种情况递归求解第三种情况通过以下方式处理从中点向左延伸取最大后缀和从中点向右延伸取最大前缀和将二者与中间元素相加。递归函数表达的是区间[l .. r]内的最大子数组和是多少算法步骤定义递归函数dfs(l, r)若l r返回负无穷无效区间求区间[l .. r]的中点m计算跨越中点的最大子数组和从m - 1向左移动到l维护最大后缀和从m 1向右移动到r维护最大前缀和与nums[m]组合递归计算左半区dfs(l, m - 1)与右半区dfs(m 1, r)的最大子数组和返回三者左、右、跨中点中的最大值以完整区间[0 .. n - 1]启动递归返回最终结果。代码实现class Solution: def maxSubArray(self, nums: List[int]) - int: def dfs(l, r): if l r: return float(-inf) m (l r) 1 leftSum rightSum curSum 0 for i in range(m - 1, l - 1, -1): curSum nums[i] leftSum max(leftSum, curSum) curSum 0 for i in range(m 1, r 1): curSum nums[i] rightSum max(rightSum, curSum) return (max(dfs(l, m - 1), dfs(m 1, r), leftSum nums[m] rightSum)) return dfs(0, len(nums) - 1)复杂度分析时间复杂度$O(n \log n)$每层扫描 O(n)共 log n 层空间复杂度$O(\log n)$递归调用栈复杂度总览解法时间复杂度空间复杂度核心思想1. 暴力枚举$O(n^2)$$O(1)$枚举所有子数组并求和2. 递归$O(2^n)$$O(n)$用flag状态机做二分决策3. 自顶向下 DP$O(n)$$O(n)$记忆化(i, flag)状态4. 自底向上 DP$O(n)$$O(n)$dp[i][1]与dp[i][0]双状态填表5. 空间优化 DP$O(n)$$O(n)$dp[i] max(nums[i], nums[i]dp[i-1])6. Kadane 算法$O(n)$$O(1)$累加和为负即重置7. 分治法$O(n \log n)$$O(\log n)$左半 / 右半 / 跨中点三分支结合 hints/maximum-subarray.md 给出的目标O(n) 时间、O(1) 空间Kadane 算法是面试与竞赛场景下的推荐答案其余解法用于理解 DP 状态设计的不同视角以及为相关问题如需要返回子数组下标、处理二维数组提供拓展基础。常见陷阱陷阱一把结果初始化为 0当数组中所有元素都为负时最大子数组和应为最大的那个负数而不是 0。若将maxSum初始化为0而非nums[0]或负无穷算法会在全负数组上错误地返回0。务必用第一个元素或一个足够小的值初始化。仓库中 java/0053-maximum-subarray.java 使用Integer.MIN_VALUE初始化即为此考虑而 Python / Go / C 等版本统一用nums[0]初始化res。陷阱二重置curSum的时机错误在 Kadane 算法中应在curSum变为负数时将其重置为 0而不是在它小于当前元素时重置。条件判断if (curSum 0) curSum 0必须放在累加当前元素之前而非之后。判断位置放错会改变子数组重启的时机导致结果错误。对照上文仓库实现可见所有语言版本都严格遵守先判断、后累加或等价地cur max(cur x, x)的顺序。仓库实战实现速览leetcode仓库以统一命名0053-maximum-subarray.ext存放本题在 12 种语言下的实现可逐一对齐验证本文各解法Python / Java / C / CJavaScript / TypeScript / C#Go / Rust / Kotlin / Swift / Ruby其中 cpp/0053-maximum-subarray.cpp 的头部注释还给出了示例输入nums [-2,1,-3,4,-1,2,1,-5,4] - 6, [4,-1,2,1]与核心思路At each point, determine if its better to add to curr sum or start over可作为快速回顾 Kadane 算法的一行式总结hints/maximum-subarray.md 则提供了从暴力到 Kadane 的递进式提示链适合用作刷题自查。若想进一步学习相关变体如包含最小值约束的变式仓库中还有 maximum-subarray-min-product 一题可供延伸阅读。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考