LeetCode-Go 题解53. Maximum Subarray 最大子数组和的动态规划详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 53. Maximum Subarray 题解文档 为主体完整讲解最大子数组和这一经典动态规划题目的状态定义、状态转移方程与边界条件并结合仓库内的 Go 实现源码 与 单元测试剖析 DP 解法和空间优化解法的底层细节。读完本文你将掌握dp[i] nums[i] dp[i-1] (dp[i-1] 0)这一核心转移方程的推导过程并能独立完成从 O(n) DP 到 O(1) 空间模拟、再到分治解法的完整思路迁移。题目描述给定一个整数数组nums找出一个具有最大和的连续子数组子数组至少包含一个元素返回其最大和。示例Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.题目大意给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例中数组[-2,1,-3,4,-1,2,1,-5,4]的最大连续子数组为[4,-1,2,1]其和为6。注意题目要求子数组是连续的因此不能对数组排序或随意跳跃选择元素这正是该题必须使用前缀连续性思维而非贪心选最大元素的原因。解题思路总览这一题可以用 DP 求解也可以不用 DP。题目要求输出数组中某个区间内数字之和最大的那个值。dp[i]表示[0,i]区间内各个子区间和的最大值状态转移方程是dp[i] nums[i] dp[i-1] (dp[i-1] 0)dp[i] nums[i] (dp[i-1] ≤ 0)。仓库针对该题提供了两种实现解法一DPmaxSubArray使用一维dp数组记录以每个位置结尾的最大子数组和解法二模拟maxSubArray1只用一个滚动变量是 Kadane 算法的空间优化形态。两者时间复杂度均为 O(n)区别仅在于空间复杂度为 O(n) 还是 O(1)。解法一动态规划DP状态定义与转移方程设dp[i]表示以nums[i]结尾的连续子数组的最大和。那么全局答案就是所有dp[i]中的最大值。对于每个位置i只有两种选择把nums[i]拼接到以nums[i-1]结尾的最优子数组后面即dp[i] nums[i] dp[i-1]以nums[i]作为新子数组的起点即dp[i] nums[i]。是否拼接取决于前一个位置的最大和dp[i-1]是否为正若dp[i-1] 0拼上去只会让总和变大取dp[i] nums[i] dp[i-1]若dp[i-1] ≤ 0它只会拖累新子数组不如从nums[i]重新开始取dp[i] nums[i]。这正是原文档给出的状态转移方程dp[i] nums[i] dp[i-1] (dp[i-1] 0) dp[i] nums[i] (dp[i-1] ≤ 0)边界条件与初始化dp[0] nums[0]以第一个元素结尾的最大子数组和只能是自己全局结果res初始化为nums[0]空数组len(nums) 0时直接返回0见源码中的防御分支。仓库源码实现仓库中的 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 }实现要点make([]int, len(nums))一次性分配dp数组避免循环内反复扩容每轮迭代同时维护res max(res, dp[i])保证最终返回的是全部dp[i]的最大值而非仅仅dp[len(nums)-1]单元素数组提前返回省去一次循环用到的max是仓库内自定义的辅助函数避免引入math包func max(a int, b int) int { if a b { return a } return b }复杂度分析维度指标说明时间复杂度O(n)仅需一次线性扫描空间复杂度O(n)需要长度为 n 的dp数组解法二滚动变量模拟Kadane 空间优化DP 解法的核心观察是dp[i]只依赖dp[i-1]因此完全可以用一个滚动变量替代整个数组。这也是 LeetCode 原题中已想出 O(n) 解法最常见的落地形态——Kadane 算法。仓库中的maxSubArray1正是这一思路的实现// 解法二 模拟 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 }逐行解读res充当滚动变量等价于 DP 中的当前以i结尾的最大子数组和每累加一个元素后先与maxSum比较更新全局最大值若res 0说明此前累积的和是负收益直接归零相当于执行了 DP 转移方程中的从nums[i]重新开始分支归零策略与 DP 中dp[i-1] ≤ 0时取nums[i]的判定在数学上完全等价因此两个解法结果一致。例如示例数组[-2,1,-3,4,-1,2,1,-5,4]的模拟过程累加到-2后归零遇到1从 1 重新累计4之前累计为1-34 2时跨越中点的最大子数组和出现在[4,-1,2,1]段累计过程会先回落再创新高最终捕获maxSum 6。该解法的空间复杂度降为 O(1)是实际面试中最推荐手写的版本。Follow Up分治解法思路原文档在 Follow up 中提示若已实现 O(n) 解法可以尝试用**分治divide and conquer**再解一遍思路更为微妙。这是原文档明确提出的延伸方向这里给出思路层面的展开仓库未收录该实现仅作思路补充将数组从中点mid一分为二最大子数组只可能出现在三种位置之一完全位于左半部分——递归求解完全位于右半部分——递归求解跨越中点——从mid向左右两侧分别扩展取左半从 mid 往左的连续最大和 右半从 mid1 往右的连续最大和三者取最大值即为答案。复杂度为 O(n log n)每层递归需要 O(n) 的时间扫描跨越中点的区间递归深度为 log n。虽然不如 O(n) 的 DP 高效但分治思想在区间查询 可合并性质类问题如线段树维护最大子段和中价值巨大。测试用例与验证仓库中的 53. Maximum Subarray_test.go 覆盖了 5 组典型用例覆盖了面试中几乎全部边界场景输入期望输出覆盖场景[-2,1,-3,4,-1,2,1,-5,4]6题目标准示例正负数混合[2,7,9,3,1]22全正数最大子数组即整个数组[2]2单元素数组[-1,-2]-1全负数取绝对值最小的单个元素[]0空数组仅 DP 版本返回 0测试采用表驱动风格para53封装输入数组ans53封装期望答案Test_Problem53依次断言并打印输入输出qs : []question53{ {para53{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}}, ans53{6}}, {para53{[]int{2, 7, 9, 3, 1}}, ans53{22}}, {para53{[]int{2}}, ans53{2}}, {para53{[]int{-1, -2}}, ans53{-1}}, {para53{[]int{}}, ans53{0}}, }其中全负数用例[-1,-2]是最容易出错的边界贪心遇到负数就丢弃的错误写法会得到0而正确结果应为-1必须从负数中挑最大的。maxSubArray通过dp[i-1] ≤ 0分支正确处理了该场景。本地运行验证仓库根目录提供了统一的测试脚本 gotest.sh对全部 leetcode 题目包执行覆盖率测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仅针对本题目目录运行go test ./leetcode/0053.Maximum-Subarray/即可看到Test_Problem53通过以及覆盖率统计与仓库 coverage.txt 中记录的 100% 测试覆盖率目标一致。总结Maximum Subarray 是动态规划入门必刷题其价值在于用最简洁的模型讲清了状态定义 转移方程 边界条件三要素状态定义dp[i]表示以nums[i]结尾的最大子数组和转移方程dp[i] nums[i] dp[i-1]当dp[i-1] 0否则dp[i] nums[i]答案所有dp[i]的最大值。仓库同时给出了 O(n) 空间的经典 DP 实现与 O(1) 空间的 Kadane 模拟实现配合覆盖空数组、单元素、全负数等边界的表驱动测试非常适合对照学习。掌握本题后可以顺势延伸至分治解法、二维最大子矩阵如 Max Sum of Rectangle No Larger Than K以及线段树维护最大子段和等进阶问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：53. Maximum Subarray 最大子数组和的动态规划详解
LeetCode-Go 题解53. Maximum Subarray 最大子数组和的动态规划详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 53. Maximum Subarray 题解文档 为主体完整讲解最大子数组和这一经典动态规划题目的状态定义、状态转移方程与边界条件并结合仓库内的 Go 实现源码 与 单元测试剖析 DP 解法和空间优化解法的底层细节。读完本文你将掌握dp[i] nums[i] dp[i-1] (dp[i-1] 0)这一核心转移方程的推导过程并能独立完成从 O(n) DP 到 O(1) 空间模拟、再到分治解法的完整思路迁移。题目描述给定一个整数数组nums找出一个具有最大和的连续子数组子数组至少包含一个元素返回其最大和。示例Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.题目大意给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例中数组[-2,1,-3,4,-1,2,1,-5,4]的最大连续子数组为[4,-1,2,1]其和为6。注意题目要求子数组是连续的因此不能对数组排序或随意跳跃选择元素这正是该题必须使用前缀连续性思维而非贪心选最大元素的原因。解题思路总览这一题可以用 DP 求解也可以不用 DP。题目要求输出数组中某个区间内数字之和最大的那个值。dp[i]表示[0,i]区间内各个子区间和的最大值状态转移方程是dp[i] nums[i] dp[i-1] (dp[i-1] 0)dp[i] nums[i] (dp[i-1] ≤ 0)。仓库针对该题提供了两种实现解法一DPmaxSubArray使用一维dp数组记录以每个位置结尾的最大子数组和解法二模拟maxSubArray1只用一个滚动变量是 Kadane 算法的空间优化形态。两者时间复杂度均为 O(n)区别仅在于空间复杂度为 O(n) 还是 O(1)。解法一动态规划DP状态定义与转移方程设dp[i]表示以nums[i]结尾的连续子数组的最大和。那么全局答案就是所有dp[i]中的最大值。对于每个位置i只有两种选择把nums[i]拼接到以nums[i-1]结尾的最优子数组后面即dp[i] nums[i] dp[i-1]以nums[i]作为新子数组的起点即dp[i] nums[i]。是否拼接取决于前一个位置的最大和dp[i-1]是否为正若dp[i-1] 0拼上去只会让总和变大取dp[i] nums[i] dp[i-1]若dp[i-1] ≤ 0它只会拖累新子数组不如从nums[i]重新开始取dp[i] nums[i]。这正是原文档给出的状态转移方程dp[i] nums[i] dp[i-1] (dp[i-1] 0) dp[i] nums[i] (dp[i-1] ≤ 0)边界条件与初始化dp[0] nums[0]以第一个元素结尾的最大子数组和只能是自己全局结果res初始化为nums[0]空数组len(nums) 0时直接返回0见源码中的防御分支。仓库源码实现仓库中的 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 }实现要点make([]int, len(nums))一次性分配dp数组避免循环内反复扩容每轮迭代同时维护res max(res, dp[i])保证最终返回的是全部dp[i]的最大值而非仅仅dp[len(nums)-1]单元素数组提前返回省去一次循环用到的max是仓库内自定义的辅助函数避免引入math包func max(a int, b int) int { if a b { return a } return b }复杂度分析维度指标说明时间复杂度O(n)仅需一次线性扫描空间复杂度O(n)需要长度为 n 的dp数组解法二滚动变量模拟Kadane 空间优化DP 解法的核心观察是dp[i]只依赖dp[i-1]因此完全可以用一个滚动变量替代整个数组。这也是 LeetCode 原题中已想出 O(n) 解法最常见的落地形态——Kadane 算法。仓库中的maxSubArray1正是这一思路的实现// 解法二 模拟 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 }逐行解读res充当滚动变量等价于 DP 中的当前以i结尾的最大子数组和每累加一个元素后先与maxSum比较更新全局最大值若res 0说明此前累积的和是负收益直接归零相当于执行了 DP 转移方程中的从nums[i]重新开始分支归零策略与 DP 中dp[i-1] ≤ 0时取nums[i]的判定在数学上完全等价因此两个解法结果一致。例如示例数组[-2,1,-3,4,-1,2,1,-5,4]的模拟过程累加到-2后归零遇到1从 1 重新累计4之前累计为1-34 2时跨越中点的最大子数组和出现在[4,-1,2,1]段累计过程会先回落再创新高最终捕获maxSum 6。该解法的空间复杂度降为 O(1)是实际面试中最推荐手写的版本。Follow Up分治解法思路原文档在 Follow up 中提示若已实现 O(n) 解法可以尝试用**分治divide and conquer**再解一遍思路更为微妙。这是原文档明确提出的延伸方向这里给出思路层面的展开仓库未收录该实现仅作思路补充将数组从中点mid一分为二最大子数组只可能出现在三种位置之一完全位于左半部分——递归求解完全位于右半部分——递归求解跨越中点——从mid向左右两侧分别扩展取左半从 mid 往左的连续最大和 右半从 mid1 往右的连续最大和三者取最大值即为答案。复杂度为 O(n log n)每层递归需要 O(n) 的时间扫描跨越中点的区间递归深度为 log n。虽然不如 O(n) 的 DP 高效但分治思想在区间查询 可合并性质类问题如线段树维护最大子段和中价值巨大。测试用例与验证仓库中的 53. Maximum Subarray_test.go 覆盖了 5 组典型用例覆盖了面试中几乎全部边界场景输入期望输出覆盖场景[-2,1,-3,4,-1,2,1,-5,4]6题目标准示例正负数混合[2,7,9,3,1]22全正数最大子数组即整个数组[2]2单元素数组[-1,-2]-1全负数取绝对值最小的单个元素[]0空数组仅 DP 版本返回 0测试采用表驱动风格para53封装输入数组ans53封装期望答案Test_Problem53依次断言并打印输入输出qs : []question53{ {para53{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}}, ans53{6}}, {para53{[]int{2, 7, 9, 3, 1}}, ans53{22}}, {para53{[]int{2}}, ans53{2}}, {para53{[]int{-1, -2}}, ans53{-1}}, {para53{[]int{}}, ans53{0}}, }其中全负数用例[-1,-2]是最容易出错的边界贪心遇到负数就丢弃的错误写法会得到0而正确结果应为-1必须从负数中挑最大的。maxSubArray通过dp[i-1] ≤ 0分支正确处理了该场景。本地运行验证仓库根目录提供了统一的测试脚本 gotest.sh对全部 leetcode 题目包执行覆盖率测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仅针对本题目目录运行go test ./leetcode/0053.Maximum-Subarray/即可看到Test_Problem53通过以及覆盖率统计与仓库 coverage.txt 中记录的 100% 测试覆盖率目标一致。总结Maximum Subarray 是动态规划入门必刷题其价值在于用最简洁的模型讲清了状态定义 转移方程 边界条件三要素状态定义dp[i]表示以nums[i]结尾的最大子数组和转移方程dp[i] nums[i] dp[i-1]当dp[i-1] 0否则dp[i] nums[i]答案所有dp[i]的最大值。仓库同时给出了 O(n) 空间的经典 DP 实现与 O(1) 空间的 Kadane 模拟实现配合覆盖空数组、单元素、全负数等边界的表驱动测试非常适合对照学习。掌握本题后可以顺势延伸至分治解法、二维最大子矩阵如 Max Sum of Rectangle No Larger Than K以及线段树维护最大子段和等进阶问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考