【力扣100题】56.最大子数组和

题目描述给你一个整数数组 nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组数组中的一个连续部分。示例示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 示例 2 输入nums [1] 输出1 示例 3 输入nums [5,4,-1,7,8] 输出23 约束1 nums.length 10^5-10^4 nums[i] 10^4 进阶如果已经实现 O(n) 解法尝试使用分治法解题思路总览方法核心思想时间复杂度空间复杂度备注暴力枚举枚举所有子数组O(n^2)O(1)会超时动态规划dp[i] max(dp[i-1] num, num)O(n)O(n)一维 DP贪心Kadanepref max(pref num, num)O(n)O(1)最优解分治法递归处理左右和跨越中点的情况O(n)O(logn)进阶要求一、贪心算法Kadane 算法推荐核心思想遍历数组维护两个变量pref以当前元素结尾的最大子数组和ans遍历过程中pref的最大值即最终答案关键决策对于每个元素 num是把它加入之前的子数组还是从它开始重新作为一个新子数组如果 pref num num说明之前的累加会减少和不如从 num 重新开始 如果 pref num num把 num 加入子数组代码实现classSolution{public:intmaxSubArray(vectorintnums){intpref0;// 以当前元素结尾的最大子数组和intansnums[0];// 全局最大子数组和for(autonum:nums){// 决策是从 num 重新开始还是把 num 加入之前的子数组prefmax(prefnum,num);// 更新答案ansmax(ans,pref);}returnans;}};二、算法流程图以 nums [-2,1,-3,4,-1,2,1,-5,4] 为例遍历过程 初始状态 pref 0 ans nums[0] -2 i0, num-2: pref max(0 (-2), -2) max(-2, -2) -2 ans max(-2, -2) -2 子数组: [-2] i1, num1: pref max(-2 1, 1) max(-1, 1) 1 ans max(-2, 1) 1 子数组: [1] i2, num-3: pref max(1 (-3), -3) max(-2, -3) -2 ans max(1, -2) 1 子数组: [1, -3]? 不对重新开始所以是 [-3] i3, num4: pref max(-2 4, 4) max(2, 4) 4 ans max(1, 4) 4 子数组: [4] i4, num-1: pref max(4 (-1), -1) max(3, -1) 3 ans max(4, 3) 4 子数组: [4, -1] i5, num2: pref max(3 2, 2) max(5, 2) 5 ans max(4, 5) 5 子数组: [4, -1, 2] i6, num1: pref max(5 1, 1) max(6, 1) 6 ans max(5, 6) 6 子数组: [4, -1, 2, 1] - 最大和 6 i7, num-5: pref max(6 (-5), -5) max(1, -5) 1 ans max(6, 1) 6 子数组: [4, -1, 2, 1, -5] i8, num4: pref max(1 4, 4) max(5, 4) 5 ans max(6, 5) 6 子数组: [4] 最终答案ans 6 最长子数组[4, -1, 2, 1]三、逐行解析对照原题代码intmaxSubArray(vectorintnums){intpref0;// 初始化为 0表示空子数组的和intansnums[0];// ans 必须初始化为 nums[0]因为子数组最少包含一个元素for(autonum:nums){// pref: 以 num 结尾的最大子数组和// max(pref num, num) 的含义// - pref num : 把 num 加入之前的子数组// - num : 从 num 重新开始之前的累加不如从头来prefmax(prefnum,num);// ans: 历史上最大的 pref即全局最大子数组和ansmax(ans,pref);}returnans;}关键点解释语句含义pref以当前遍历到的元素结尾的最大子数组和pref max(pref num, num)决策是否延续之前的子数组ans记录遍历过程中最大的prefans nums[0]子数组最少包含一个元素所以 ans 不能初始化为 0为什么 pref 可以初始化为 0因为 max(0 num, num) max(num, num) num 对于第一个元素 num -2 pref max(0 (-2), -2) -2 - 正确 这相当于从第一个元素开始之前的空子数组没有贡献所以 pref num四、图解贪心选择nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] pref 变化过程折线图 6 | ____ 5 | ____/ \____ 4 | ____/ * ---- ans 6 3 | ____/ * ---- 2 | ____/ * ---- 1 | __/ * ---- 0 |/ * * ---- -1 | * * ---- -2 | * * ---- -3 | * ---- -4 ------------------------------ 0 1 2 3 4 5 6 7 8 * pref 在该位置的取值 关键决策点 - i1: pref-2 - pref1 (重新开始有利) - i2: pref1 - pref-2 (重新开始有利) - i3: pref-2 - pref4 (重新开始有利) - i6: pref5 - pref6 (延续加入1)五、动态规划解法对比思路dp[i] 以 nums[i] 结尾的最大子数组和状态转移方程dp[i] max(dp[i-1] nums[i], nums[i])classSolution{public:intmaxSubArray(vectorintnums){intnnums.size();vectorintdp(n);dp[0]nums[0];intansdp[0];for(inti1;in;i){dp[i]max(dp[i-1]nums[i],nums[i]);ansmax(ans,dp[i]);}returnans;}};与贪心的关系贪心pref max(pref num, num) DP dp[i] max(dp[i-1] nums[i], nums[i]) pref 就是 dp[i]只是贪心只用一个变量不需要数组 时间复杂度O(n) - 相同 空间复杂度O(n) - 贪心 O(1) 更优六、分治法进阶思路将数组分成左右两部分最大子数组有三种情况完全在左半部分完全在右半部分跨越中点包含左部分末尾和右部分开头代码实现classSolution{public:intmaxSubArray(vectorintnums){returndivideConquer(nums,0,nums.size()-1);}private:intdivideConquer(vectorintnums,intleft,intright){if(leftright)returnnums[left];intmid(leftright)/2;// 1. 左半部分的最大子数组和intleftSumdivideConquer(nums,left,mid);// 2. 右半部分的最大子数组和intrightSumdivideConquer(nums,mid1,right);// 3. 跨越中点的最大子数组和// 从中点向左扫找到最大和intcrossLeftnums[mid];inttemp0;for(intimid;ileft;i--){tempnums[i];crossLeftmax(crossLeft,temp);}// 从中点1向右扫找到最大和intcrossRightnums[mid1];temp0;for(intimid1;iright;i){tempnums[i];crossRightmax(crossRight,temp);}intcrossSumcrossLeftcrossRight;// 返回三种情况的最大值returnmax(max(leftSum,rightSum),crossSum);}};复杂度方法时间复杂度空间复杂度贪心O(n)O(1)动态规划O(n)O(n)分治法O(n log n)O(logn)复杂度分析总结方法时间复杂度空间复杂度备注暴力枚举O(n^2)O(1)会超时动态规划O(n)O(n)一维 DP贪心KadaneO(n)O(1)最优解分治法O(n log n)O(logn)进阶要求面试追问 FAQ问题回答要点Q: 为什么可以这样做贪心选择当pref num num时说明之前的子数组对增大和没有帮助反而会减少。从 num 重新开始能得到更大的子数组和Q: 为什么 ans 要初始化为 nums[0]因为子数组最少包含一个元素不能为空。如果初始化为 0而 nums 全为负数答案会错误Q: 如果数组全为负数会怎样pref 会一直选择 max(负负, 负) 负数ans 会记录最大的那个负数正确Q: 分治法的时间复杂度为什么是 O(n log n)每层遍历需要 O(n)层数是 O(log n)所以总复杂度 O(n log n)Q: Kadane 算法的名称来源由日本计算机科学家今道明彦Kadane在 1984 年提出相关题目题目编号题目名称难度核心差异53最大子数组和中等基础题求最大和918环形子数组的最大和中等数组首尾相连152乘积最大子数组中等乘积而非求和需处理负数1749统计所有子数组中最大和困难所有连续子数组的和238除自身以外数组的乘积中等前缀后缀技巧总结要点内容核心思想贪心以当前元素结尾的最大子数组和 max(延续, 重新开始)关键变量pref 以 num 结尾的最大子数组和ans 全局最大和时间复杂度O(n)只需遍历一次空间复杂度O(1)只用一个变量边界处理ans 必须初始化为 nums[0]因为子数组不能为空与 DP 对比Kadane 是 DP 的空间优化版本两者本质相同Kadane 算法是处理最大子数组和的标准解法掌握后可以轻松解决环形子数组、乘积最大等变种问题。