LeetCode Hot 100 - 53. 最大子数组和（经典动态规划）

难度中等 | 面试频率⭐⭐⭐⭐⭐ 题目描述给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例示例 1text输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6。示例 2text输入nums [1] 输出1示例 3text输入nums [5,4,-1,7,8] 输出23提示1 nums.length 10^5-10^4 nums[i] 10^4 解题思路核心思想动态规划 - Kadane 算法关键思考对于以第i个元素结尾的子数组它的最大和只有两种情况单独自己nums[i]加上前面的子数组dp[i-1] nums[i]因此状态转移方程textdp[i] max(nums[i], dp[i-1] nums[i])其中dp[i]表示以i结尾的子数组的最大和。最终答案就是所有dp[i]中的最大值。 代码实现方法一动态规划标准写法javaclass Solution { public int maxSubArray(int[] nums) { int n nums.length; int[] dp new int[n]; dp[0] nums[0]; int maxSum dp[0]; for (int i 1; i n; i) { // 状态转移要么自己单干要么加入前面的队伍 dp[i] Math.max(nums[i], dp[i - 1] nums[i]); // 更新全局最大值 maxSum Math.max(maxSum, dp[i]); } return maxSum; } }方法二空间优化版推荐⭐因为dp[i]只依赖于dp[i-1]可以用一个变量代替整个数组javaclass Solution { public int maxSubArray(int[] nums) { // 初始化以前一个元素结尾的最大和 int prevMax nums[0]; int maxSum nums[0]; for (int i 1; i nums.length; i) { // 当前元素结尾的最大和 max(当前元素, 前一个最大和 当前元素) int currMax Math.max(nums[i], prevMax nums[i]); maxSum Math.max(maxSum, currMax); prevMax currMax; // 滚动更新 } return maxSum; } }方法三贪心思想javaclass Solution { public int maxSubArray(int[] nums) { int maxSum nums[0]; int currentSum nums[0]; for (int i 1; i nums.length; i) { // 如果当前和变成负数就重新开始 currentSum Math.max(nums[i], currentSum nums[i]); maxSum Math.max(maxSum, currentSum); } return maxSum; } } 代码详解方法二javapublic int maxSubArray(int[] nums) { int prevMax nums[0]; // 以第一个元素结尾的最大和就是它自己 int maxSum nums[0]; // 全局最大和初始化为第一个元素 for (int i 1; i nums.length; i) { // 核心对于当前元素要么重新开始要么接续前面的子数组 int currMax Math.max(nums[i], prevMax nums[i]); // 更新全局最大值 maxSum Math.max(maxSum, currMax); // 滚动到下一个位置 prevMax currMax; } return maxSum; }理解Math.max(nums[i], prevMax nums[i])这个选择回答了要不要延续之前的子数组情况说明例子prevMax nums[i] nums[i]延续更优prevMax3, nums[i]2→ 延续得 5 2prevMax nums[i] nums[i]重新开始更优prevMax-2, nums[i]3→ 重新开始得 3 1️ 图解示例以nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]为例inums[i]prevMax上一个结尾最大和currMax max(nums[i], prevMaxnums[i])maxSum0-2-2初始-2-211-2max(1, -21 -1) 1max(-2,1)12-31max(-3, 1-3 -2) -2max(1,-2)134-2max(4, -242) 4max(1,4)44-14max(-1, 4-13) 3max(4,3)4523max(2, 325) 5max(4,5)5615max(1, 516) 6max(5,6)67-56max(-5, 6-51) 1max(6,1)6841max(4, 145) 5max(6,5)6最终答案6✅ 复杂度分析方法时间复杂度空间复杂度DP 数组O(n)O(n)空间优化 DPO(n)O(1)⭐贪心O(n)O(1)✅ 测试验证javapublic static void main(String[] args) { Solution solution new Solution(); // 示例 1 int[] nums1 {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(solution.maxSubArray(nums1)); // 输出: 6 // 示例 2 int[] nums2 {1}; System.out.println(solution.maxSubArray(nums2)); // 输出: 1 // 示例 3 int[] nums3 {5,4,-1,7,8}; System.out.println(solution.maxSubArray(nums3)); // 输出: 23 // 边界测试全负数 int[] nums4 {-1,-2,-3,-4}; System.out.println(solution.maxSubArray(nums4)); // 输出: -1最大的负数 // 边界测试全正数 int[] nums5 {1,2,3,4,5}; System.out.println(solution.maxSubArray(nums5)); // 输出: 15全部相加 } 关键点总结要点说明核心思想Kadane 算法动态规划状态定义dp[i] 以i结尾的最大子数组和状态转移dp[i] max(nums[i], dp[i-1] nums[i])空间优化只需一个变量滚动更新时间复杂度O(n)空间复杂度O(1)⚠️ 常见错误错误理解状态dp[i]不是前 i 个元素的最大子数组和而是以 i 结尾的最大子数组和忘记处理全负数如果全部是负数应该返回最大的那个负数不是 0初始化错误maxSum不能初始化为 0因为全负数时答案为负数java// ❌ 错误写法 int maxSum 0; // ✅ 正确写法 int maxSum nums[0];边界条件数组长度为 1 时直接返回该元素 举一反三相关题目题目难度解法要点152. 乘积最大子数组中等同时维护最大值和最小值因为负数×负数正数918. 环形子数组的最大和中等两种情况正常 Kadane 或 总和 - 最小子数组和121. 买卖股票的最佳时机简单转化为最大子数组和问题变形返回子数组本身如果题目要求返回最大和的子数组可以稍作修改javapublic int[] maxSubArrayWithIndices(int[] nums) { int prevMax nums[0]; int maxSum nums[0]; int start 0, end 0; int tempStart 0; for (int i 1; i nums.length; i) { if (nums[i] prevMax nums[i]) { // 重新开始 prevMax nums[i]; tempStart i; } else { // 延续 prevMax prevMax nums[i]; } if (prevMax maxSum) { maxSum prevMax; start tempStart; end i; } } return Arrays.copyOfRange(nums, start, end 1); } 面试技巧面试官可能会问Q能否用分治法解决A可以时间复杂度 O(n log n)。将数组分成两半最大子数组要么在左半、要么在右半、要么跨越中点。Q如果数组长度很大10^6算法还适用吗A适用O(n) 的 Kadane 算法非常高效即使 10^6 也只需约 10^6 次操作。Q如何证明 Kadane 算法的正确性A可以用归纳法。假设dp[i-1]是以 i-1 结尾的最大子数组和那么以 i 结尾的最大子数组要么包含 i-1dp[i-1] nums[i]要么不包含nums[i]。 相关链接LeetCode 原题53. 最大子数组和Kadane 算法详解维基百科 欢迎在评论区讨论交流如果这篇文章对你有帮助请点赞支持 关注我持续更新 LeetCode Hot 100 题解