LeetCode 题解 53. 最大子序和（Maximum Subarray）：暴力、前缀和、分治与动态规划五种解法全解析

LeetCode 题解 53. 最大子序和Maximum Subarray暴力、前缀和、分治与动态规划五种解法全解析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于本仓库leetcode 题解集中的 53.maximum-sum-subarray-en.md及其中文对照版 53.maximum-sum-subarray-cn.md系统展开完整讲解 LeetCode 53「最大子序和」的五种解法原始暴力O(n³)、前缀和 暴力O(n²)、优化前缀和O(n)、分治法O(nlogn)与动态规划O(n)。读完本文你将掌握从暴力出发逐步优化到线性解法的完整思维路径理解前缀和与动态规划这两类核心技巧的推导过程并可直接套用仓库提供的 Java、Python3、JavaScript 三语言实现。题目回顾给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大为 6。进阶要求如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的分治法求解。本题在仓库 README.md 的题解目录中作为数组/前缀和类题目收录是理解「连续子数组区间和」问题的经典入门题。仓库的 前缀和专题 指出当题目要求「连续」时滑动窗口与前缀和都是优化时间复杂度的重要武器而本题正是把这一思想发挥到极致的代表。解法一原始暴力枚举O(n³)TLE核心思路子数组由首尾位置(l, r)唯一确定因此先用两层for循环枚举所有可能的[l, r]组合再用第三层循环从l累加到r计算当前子数组和最后用全局变量maxSum记录最大值。这种方式代码最简单但性能极差时间复杂度为 O(n³)在 LeetCode 上必然超时TLE仅作为分析的起点。复杂度分析时间复杂度O(n³)n 为数组长度空间复杂度O(1)解法二前缀和 暴力枚举O(n²)AC核心思路暴力的瓶颈在于每次都要重新累加子数组和。引入前缀和prefixSum预处理后任意区间[l, r]的和可以在 O(1) 时间内得到subarraySum prefixSum[r] - prefixSum[l - 1]再用全局变量maxSum与每个子数组和比较maxSum max(maxSum, subarraySum)这样把时间复杂度降到 O(n²)空间换时间在 LeetCode 上可以 AC。优化提示如果不额外开数组而是直接修改原数组使其表示前缀和则空间复杂度可由 O(n) 降为 O(1)。复杂度分析时间复杂度O(n²)n 为数组长度空间复杂度O(n)前缀和数组长度 n用原数组就地改写可降至 O(1)三语言实现仓库原文代码Javaclass MaximumSubarrayPrefixSum { public int maxSubArray(int[] nums) { int len nums.length; int maxSum Integer.MIN_VALUE; int sum 0; for (int i 0; i len; i) { sum 0; for (int j i; j len; j) { sum nums[j]; maxSum Math.max(maxSum, sum); } } return maxSum; } }Python3(TLE)import sys class Solution: def maxSubArray(self, nums: List[int]) - int: n len(nums) maxSum -sys.maxsize sum 0 for i in range(n): sum 0 for j in range(i, n): sum nums[j] maxSum max(maxSum, sum) return maxSumJavaScriptfunction LSS(list) { const len list.length; let max -Number.MAX_VALUE; let sum 0; for (let i 0; i len; i) { sum 0; for (let j i; j len; j) { sum list[j]; if (sum max) { max sum; } } } return max; }解法三优化前缀和O(n)O(1) 空间解法二仍是 O(n²)能否继续优化答案是肯定的——这是解法二到解法四分治与解法五DP之间承上启下的关键一步该思路由仓库作者 lucifer 提供。核心推导定义S(i)为数组[0, i]的前缀和则区间[i, j]的和为S(j) - S(i - 1)我们只需一次遍历计算出所有的S(i)i 0, 1, 2, ..., n-1同时维护遍历到当前位置之前的最小前缀和minSum即S(k)的最小值k i那么以i结尾的最大子数组和就是maxSum max(maxSum, S(i) - minSum)其中S(i) - minSum的含义是用当前前缀和减去历史上最小的前缀和得到以当前位置结尾的、和最大的子数组。整个过程只维护两个变量minSum与maxSum不需要额外数组。复杂度分析时间复杂度O(n)n 为数组长度空间复杂度O(1)三语言实现Javaclass MaxSumSubarray { public int maxSubArray3(int[] nums) { int maxSum nums[0]; int sum 0; int minSum 0; for (int num : nums) { // prefix Sum sum num; // update maxSum maxSum Math.max(maxSum, sum - minSum); // update minSum minSum Math.min(minSum, sum); } return maxSum; } }Python3class Solution: def maxSubArray(self, nums: List[int]) - int: n len(nums) maxSum nums[0] minSum sum 0 for i in range(n): sum nums[i] maxSum max(maxSum, sum - minSum) minSum min(minSum, sum) return maxSumJavaScriptfunction LSS(list) { const len list.length; let max list[0]; let min 0; let sum 0; for (let i 0; i len; i) { sum list[i]; if (sum - min max) max sum - min; if (sum min) { min sum; } } return max; }为什么 minSum 初始为 0因为S(k)允许取空前缀k -1和为 0这保证整个数组本身从头开始的连续段也能被正确计入最大和例如数组[1, 2, 3]的最大子数组就是[1, 2, 3]本身此时minSum 0必不可少。解法四分治法O(nlogn)分治法的思想是把数组从中间一分为二最大子数组和只可能出现在三种位置完全在左半部分left nums[0]...nums[m-1]递归求解左半部分的最大子数组和完全在右半部分right nums[m1]...nums[n-1]递归求解右半部分的最大子数组和跨越中间元素nums[m]从中间元素出发向左求连续后缀最大值leftMaxSum向右求连续前缀最大值rightMaxSum跨越中点的最大和为crossMaxSum leftMaxSum rightMaxSum nums[m]最终答案取三者最大值max(left, right, crossMaxSum)下图以示例数组[-2,1,-3,4,-1,2,1,-5,4]展示了分治的分解Divide与合并Conquer过程蓝色箭头表示递归拆分橙色箭头表示逐层合并取max(left, right, cross)最终得到全局最大和 6对应子数组[4,-1,2,1]。复杂度分析时间复杂度O(nlogn)n 为数组长度。每一层的跨中点扫描需要 O(n)递归深度为 O(logn)空间复杂度仓库英文版标注为 O(1)不计递归调用栈若计入递归栈深度则为 O(logn)中文版 53.maximum-sum-subarray-cn.md 即标注为 O(logn)两版表述的差异在于是否把递归调用栈计入空间开销三语言实现Javaclass MaximumSubarrayDivideConquer { public int maxSubArrayDividConquer(int[] nums) { if (nums null || nums.length 0) return 0; return helper(nums, 0, nums.length - 1); } private int helper(int[] nums, int l, int r) { if (l r) return Integer.MIN_VALUE; int mid (l r) 1; int left helper(nums, l, mid - 1); int right helper(nums, mid 1, r); int leftMaxSum 0; int sum 0; // left surfix maxSum start from index mid - 1 to l for (int i mid - 1; i l; i--) { sum nums[i]; leftMaxSum Math.max(leftMaxSum, sum); } int rightMaxSum 0; sum 0; // right prefix maxSum start from index mid 1 to r for (int i mid 1; i r; i) { sum nums[i]; rightMaxSum Math.max(sum, rightMaxSum); } // max(left, right, crossSum) return Math.max(leftMaxSum rightMaxSum nums[mid], Math.max(left, right)); } }Python3import sys class Solution: def maxSubArray(self, nums: List[int]) - int: return self.helper(nums, 0, len(nums) - 1) def helper(self, nums, l, r): if l r: return -sys.maxsize mid (l r) // 2 left self.helper(nums, l, mid - 1) right self.helper(nums, mid 1, r) left_suffix_max_sum right_prefix_max_sum 0 sum 0 for i in reversed(range(l, mid)): sum nums[i] left_suffix_max_sum max(left_suffix_max_sum, sum) sum 0 for i in range(mid 1, r 1): sum nums[i] right_prefix_max_sum max(right_prefix_max_sum, sum) cross_max_sum left_suffix_max_sum right_prefix_max_sum nums[mid] return max(cross_max_sum, left, right)JavaScriptfunction helper(list, m, n) { if (m n) return list[m]; let sum 0; let lmax -Number.MAX_VALUE; let rmax -Number.MAX_VALUE; const mid ((n - m) 1) m; const l helper(list, m, mid); const r helper(list, mid 1, n); for (let i mid; i m; i--) { sum list[i]; if (sum lmax) lmax sum; } sum 0; for (let i mid 1; i n; i) { sum list[i]; if (sum rmax) rmax sum; } return Math.max(l, r, lmax rmax); } function LSS(list) { return helper(list, 0, list.length - 1); }实现细节提醒Java 中(l r) 1是无符号右移取中点避免l r溢出Python 的//与 JS 的同理都是向下取整Java/Python 版本的递归边界是l r时返回Integer.MIN_VALUE/-sys.maxsize保证不会干扰max计算跨中点扫描时左右两侧的起始累加值从 0 开始允许「只取中间元素一侧」的情况存在。解法五动态规划O(n)O(1) 空间动态规划的难点在于找到状态转移方程与初始状态。状态定义dp[i] - 以索引 i 结尾的最大子数组和状态转移方程dp[i] max(dp[i - 1] nums[i], nums[i])含义是以i结尾的最大子数组和要么把nums[i]续在「以i-1结尾的最大子数组」之后dp[i-1] nums[i]要么从nums[i]重新开始nums[i]两者取大。初始状态dp[0] nums[0]空间优化观察转移方程可知每一步只依赖前一个状态dp[i-1]因此不需要开长度为 n 的数组只需两个变量currMaxSum以当前位置 i 结尾的最大子数组和即dp[i]的滚动值maxSum全局最大子数组和currMaxSum max(currMaxSum nums[i], nums[i]) maxSum max(currMaxSum, maxSum)下图展示了 DP 解法在示例数组上的完整状态演变currMaxSum数组记录以每个位置结尾的最大子数组和[-2, 1, -2, 4, 3, 5, 6, 1, 5]maxSum数组记录到当前位置为止的全局最大值[-2, 1, 1, 4, 4, 5, 6, 6, 6]最终答案 6 对应子数组[4, -1, 2, 1]。复杂度分析时间复杂度O(n)n 为数组长度空间复杂度O(1)仅两个变量若不优化、使用完整 dp 数组则为 O(n)三语言实现Javaclass MaximumSubarrayDP { public int maxSubArray(int[] nums) { int currMaxSum nums[0]; int maxSum nums[0]; for (int i 1; i nums.length; i) { currMaxSum Math.max(currMaxSum nums[i], nums[i]); maxSum Math.max(maxSum, currMaxSum); } return maxSum; } }Python3class Solution: def maxSubArray(self, nums: List[int]) - int: n len(nums) max_sum_ending_curr_index max_sum nums[0] for i in range(1, n): max_sum_ending_curr_index max(max_sum_ending_curr_index nums[i], nums[i]) max_sum max(max_sum_ending_curr_index, max_sum) return max_sumJavaScript原地改写数组的紧凑写法function LSS(list) { const len list.length; let max list[0]; for (let i 1; i len; i) { list[i] Math.max(0, list[i - 1]) list[i]; if (list[i] max) max list[i]; } return max; }注意JS 版本把dp[i-1]直接覆盖写到list[i-1]上Math.max(0, list[i - 1])相当于「如果前一个状态为负则舍弃、从当前元素重新开始」与标准转移方程dp[i] max(dp[i-1] nums[i], nums[i])等价因为max(0, x) y max(y, x y)。关键点总结回顾整个推导过程五种解法层层递进暴力解枚举所有子数组首尾组合逐个求和取最大。优化手段是引入前缀和预处理把区间和查询降到 O(1)前缀和 暴力O(n²)空间换时间可作为暴力到线性解法的过渡优化前缀和一次遍历维护「当前前缀和」与「历史最小前缀和」S(i) - minSum即得到以 i 结尾的最大子数组和O(n) 且 O(1) 空间分治法从中间位置将数组一分为二分别递归求左半、右半最大子数组和再计算跨越中点的最大和三者取最大return max(leftMaxSum, rightMaxSum, crossMaxSum)动态规划找到状态转移方程dp[i] max(dp[i-1] nums[i], nums[i])与初始状态dp[0] nums[0]用两个变量滚动更新即可是理解「以 i 结尾」这类 DP 状态定义的经典范例。从 O(n³) → O(n²) → O(nlogn) → O(n) 的演进路径展示了「暴力枚举 → 预处理优化 → 分治 → 动态规划」这一完整的算法优化思维链对解决同类「连续子数组/子序列」问题具有普适的指导意义。扩展思考Follow Up仓库文档在结尾抛出了两个值得深入思考的扩展方向二维矩阵版如果输入是 M×N 的矩阵如何计算最大子矩阵的和可以从「对列做前缀和压缩、再对行跑一维最大子数组和」的思路入手把问题化归到本题乘积版如果要求最大子数组的乘积呢与最大和相比有何区别关键差异在于负数乘负数会变大因此不能只维护最大值还需同时维护最小值。仓库中的 152. 乘积最大子数组 正是这一变形的完整解答其核心关键点是「同时记录乘积最大值和乘积最小值」。相似题目152. 乘积最大子数组Maximum Product Subarray把「和」换成「积」需要同时维护最大与最小值978. 最长湍流子数组Longest Turbulent Subarray同样考察连续子数组的遍历与状态维护。延伸阅读仓库内专题动态规划专题dynamic-programming.md从记忆化递归讲起系统讲解状态转移与 DP 公式的推导方法论帮助理解解法五中dp[i]状态定义的由来前缀和专题prefix.md指出「连续」类问题中前缀和与滑动窗口对时间复杂度优化的重要意义解法二、三正是前缀和思想的直接应用本题题解目录收录位置README.md同时可参考其英文版 53.maximum-sum-subarray-en.md。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考