LeetCode 53. Maximum Subarray 题解Go 语言 DP 与模拟双解法全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 展开完整讲解 LeetCode 第 53 题「最大子数组和」Maximum Subarray给定整数数组找出和最大的连续子数组并返回其和。仓库同时提供了动态规划DP与模拟Kadane 算法变体两种 O(n) 解法并附带完整的单元测试。读完本文你将掌握这道经典题的状态转移方程推导、两种解法的代码实现与复杂度对比并能通过仓库测试用例与覆盖率脚本完成本地验证。题目概述问题定义给定一个整数数组nums找到一个具有最大和的连续子数组子数组至少包含一个元素返回其最大和。原题完整描述见 0053.Maximum-Subarray.md仓库还提供了中文版题目说明与题解 README。示例Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.Follow up如果你已经想出了 O(n) 的解法尝试用**分治法divide and conquer**再实现一种解法——这更考验对区间划分的理解。题目大意题目要求输出数组中某个区间内数字之和最大的那个值。注意子数组必须是连续的且至少要包含一个元素因此全为负数时也必须取一个元素取最大的那个负数不能返回空区间。解题思路总览这一题可以用 DP 求解也可以不用 DP。文档中给出了两条主线DP 解法用dp[i]表示[0,i]区间内各个子区间和的最大值通过状态转移方程递推求解模拟解法线性扫描累加一旦累加和为负就丢弃重新累加本质是 Kadane 算法的原地in-place写法空间复杂度降为 O(1)分治法Follow up 要求把数组从中点切分成左右两半最大子数组要么完全在左半、要么完全在右半、要么跨越中点递归求解后合并。下面结合仓库源码逐一展开。解法一动态规划DP状态定义与转移方程设dp[i]表示以nums[i]结尾的最大子数组和文档中的表述为[0,i]区间内各个子区间和的最大值两者在递推上是等价的。核心决策是接上前面的连续段还是从当前元素重新开始。状态转移方程与原文档完全一致dp[i] nums[i] dp[i-1] (dp[i-1] 0) dp[i] nums[i] (dp[i-1] ≤ 0)直觉解释如果前一个位置结尾的最大子段和dp[i-1]是正数把它接到nums[i]前面只会让总和更大所以继承如果dp[i-1]是负数或零接上它只会拖累当前结果不如从nums[i]重新开一个新子数组。最终答案是所有dp[i]中的最大值res max(res, dp[i])。仓库源码实现仓库实现位于 53. Maximum Subarray.go// 解法一 DP func maxSubArray(nums []int) int { if len(nums) 0 { return 0 } if len(nums) 1 { return nums[0] } dp, res : make([]int, len(nums)), nums[0] dp[0] nums[0] for i : 1; i len(nums); i { if dp[i-1] 0 { dp[i] nums[i] dp[i-1] } else { dp[i] nums[i] } res max(res, dp[i]) } return res } func max(a int, b int) int { if a b { return a } return b }实现要点边界防护空数组返回 0单元素数组直接返回nums[0]这两个分支保证后续访问dp[0]、dp[i-1]不会越界dp[0] nums[0]作为递推起点res初始化为nums[0]而非 0避免全负数组时res恒为 0 的错误依赖的max辅助函数在同一个文件中定义见 53. Maximum Subarray.go。复杂度分析时间复杂度O(n)仅需一趟线性扫描空间复杂度O(n)dp数组与输入等长。实际可以只用两个变量滚动递推降到 O(1)仓库此版为了直观展示状态转移保留了完整dp数组。解法二模拟Kadane 变体算法思想不借助dp数组用一个变量res累积当前子段和用一个变量maxSum记录历史最大值。扫描时每次把nums[p]累加到res先更新maxSum一旦res变为负数说明当前子段继续向后延伸只会减少总和立即把res重置为 0从下一个位置重新累积。这本质上是 Kadane 算法的经典写法。仓库源码实现仓库实现位于 53. Maximum Subarray.go// 解法二 模拟 func maxSubArray1(nums []int) int { if len(nums) 1 { return nums[0] } maxSum, res, p : nums[0], 0, 0 for p len(nums) { res nums[p] if res maxSum { maxSum res } if res 0 { res 0 } p } return maxSum }实现要点maxSum初始化为nums[0]保证全负数组也能正确返回最大的那个负数累加后先更新maxSum再判断是否重置顺序不可颠倒否则负数段会被提前清零而漏计注意该解法只对单元素数组做了防护没有空数组分支。仓库测试文件 53. Maximum Subarray_test.go 中调用maxSubArray1前特意用if len(p.one) 0做了保护这一点与 DP 版对空输入的处理策略不同是两者在健壮性上的差异。复杂度分析时间复杂度O(n)空间复杂度O(1)只使用常数个变量比 DP 版更省空间。Follow Up分治法思路原题 Follow up 建议在 O(n) 解法之外再用分治法实现一遍因为这种思路更 subtle微妙。仓库源码中未提供分治实现以下为对 Follow up 的补充理解把数组从中点mid一分为二那么最大子数组必然落在三种情况之一完全位于左半区间[left, mid]递归求解完全位于右半区间[mid1, right]递归求解跨越中点从mid向左扩展求最大后缀和从mid1向右扩展求最大前缀和两者相加。递归的合并步情况 3需要 O(n) 时间扫描一遍跨中点的元素因此总时间复杂度满足递推式T(n) 2T(n/2) O(n)即 O(n log n)慢于前两种线性解法但它体现的区间划分—递归—合并思想是很多高级问题如线段树维护区间最大子段和的基础。如果你想自行补充该实现可以基于 53. Maximum Subarray.go 新建一个递归函数作为练习。测试用例与本地验证仓库内置测试测试文件 53. Maximum Subarray_test.go 定义了question53/para53/ans53结构体组织用例共覆盖 5 组输入输入期望输出覆盖场景[-2,1,-3,4,-1,2,1,-5,4]6题目官方示例正负交错[2,7,9,3,1]22全部为正答案即整个数组[2]2单元素数组[-1,-2]-1全部为负取最大负数[]0空数组仅 DP 版可处理每组用例在测试中都会打印输入与输出fmt.Printf(【input】:%v ... 【output】:%v ...)并同时调用maxSubArray与maxSubArray1验证两个解法见 53. Maximum Subarray_test.go。运行测试与覆盖率在仓库根目录执行以下命令即可运行该题及其余题目的全部测试# 运行单个题的测试 go test -v ./leetcode/0053.Maximum-Subarray/ # 生成整个 leetcode 包的覆盖率文件仓库脚本要求 Go 1.10 bash gotest.shgotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对 leetcode 下所有包生成单一合法的coverage.txt覆盖率文件这是本仓库维持100% test coverage质量门槛的基础设施。模块信息与 Go 版本要求go 1.19见仓库根目录 go.mod。总结LeetCode 53. Maximum Subarray 是动态规划与贪心思想交汇的入门经典DP 解法通过dp[i] nums[i] dp[i-1] (dp[i-1] 0)的状态转移方程把是否延续前段的决策形式化是理解更复杂区间 DP 问题的基石**模拟解法Kadane 变体**用累加—更新—遇负清零三步行云流水地完成 O(n) 时间、O(1) 空间的求解代码更短但边界顺序先更新再清零需要格外小心分治法作为 Follow up 提供了区间划分视角尽管复杂度 O(n log n) 并非最优却是理解线段树等高级结构的前置概念。仓库在 0053.Maximum-Subarray 目录下同时给出了源码、测试与题解 README配合 gotest.sh 的覆盖率脚本可以完整复现实现—验证—量化的工程化刷题闭环。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考