【力扣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) 解法，尝试使用分治法

解题思路总览

一、贪心算法（Kadane 算法，推荐）

核心思想

遍历数组，维护两个变量：

• pref：以当前元素结尾的最大子数组和
• ans：遍历过程中pref的最大值，即最终答案

关键决策：对于每个元素 num，是把它加入之前的子数组，还是从它开始重新作为一个新子数组？

如果 pref + num < num，说明之前的累加会减少和，不如从 num 重新开始 如果 pref + num >= num，把 num 加入子数组

代码实现

classSolution{public:intmaxSubArray(vector<int>&nums){intpref=0;// 以当前元素结尾的最大子数组和intans=nums[0];// 全局最大子数组和for(autonum:nums){// 决策：是从 num 重新开始，还是把 num 加入之前的子数组？pref=max(pref+num,num);// 更新答案ans=max(ans,pref);}returnans;}};

二、算法流程图

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例

遍历过程： 初始状态： pref = 0 ans = nums[0] = -2 i=0, num=-2: pref = max(0 + (-2), -2) = max(-2, -2) = -2 ans = max(-2, -2) = -2 子数组: [-2] i=1, num=1: pref = max(-2 + 1, 1) = max(-1, 1) = 1 ans = max(-2, 1) = 1 子数组: [1] i=2, num=-3: pref = max(1 + (-3), -3) = max(-2, -3) = -2 ans = max(1, -2) = 1 子数组: [1, -3]? 不对，重新开始所以是 [-3] i=3, num=4: pref = max(-2 + 4, 4) = max(2, 4) = 4 ans = max(1, 4) = 4 子数组: [4] i=4, num=-1: pref = max(4 + (-1), -1) = max(3, -1) = 3 ans = max(4, 3) = 4 子数组: [4, -1] i=5, num=2: pref = max(3 + 2, 2) = max(5, 2) = 5 ans = max(4, 5) = 5 子数组: [4, -1, 2] i=6, num=1: pref = max(5 + 1, 1) = max(6, 1) = 6 ans = max(5, 6) = 6 子数组: [4, -1, 2, 1] <- 最大和 6！ i=7, num=-5: pref = max(6 + (-5), -5) = max(1, -5) = 1 ans = max(6, 1) = 6 子数组: [4, -1, 2, 1, -5] i=8, num=4: pref = max(1 + 4, 4) = max(5, 4) = 5 ans = max(6, 5) = 6 子数组: [4] 最终答案：ans = 6 最长子数组：[4, -1, 2, 1]

三、逐行解析（对照原题代码）

intmaxSubArray(vector<int>&nums){intpref=0;// 初始化为 0，表示"空子数组的和"intans=nums[0];// ans 必须初始化为 nums[0]，因为子数组最少包含一个元素for(autonum:nums){// pref: 以 num 结尾的最大子数组和// max(pref + num, num) 的含义：// - pref + num : 把 num 加入之前的子数组// - num : 从 num 重新开始（之前的累加不如从头来）pref=max(pref+num,num);// ans: 历史上最大的 pref，即全局最大子数组和ans=max(ans,pref);}returnans;}

关键点解释

为什么 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 在该位置的取值 关键决策点： - i=1: pref=-2 -> pref=1 (重新开始有利) - i=2: pref=1 -> pref=-2 (重新开始有利) - i=3: pref=-2 -> pref=4 (重新开始有利) - i=6: pref=5 -> pref=6 (延续，加入1)

五、动态规划解法（对比）

思路

dp[i]= 以 nums[i] 结尾的最大子数组和

状态转移方程：

dp[i] = max(dp[i-1] + nums[i], nums[i])

classSolution{public:intmaxSubArray(vector<int>&nums){intn=nums.size();vector<int>dp(n);dp[0]=nums[0];intans=dp[0];for(inti=1;i<n;i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);ans=max(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) 更优

六、分治法（进阶）

思路

将数组分成左右两部分，最大子数组有三种情况：

1. 完全在左半部分
2. 完全在右半部分
3. 跨越中点（包含左部分末尾和右部分开头）

代码实现

classSolution{public:intmaxSubArray(vector<int>&nums){returndivideConquer(nums,0,nums.size()-1);}private:intdivideConquer(vector<int>&nums,intleft,intright){if(left==right)returnnums[left];intmid=(left+right)/2;// 1. 左半部分的最大子数组和intleftSum=divideConquer(nums,left,mid);// 2. 右半部分的最大子数组和intrightSum=divideConquer(nums,mid+1,right);// 3. 跨越中点的最大子数组和// 从中点向左扫，找到最大和intcrossLeft=nums[mid];inttemp=0;for(inti=mid;i>=left;i--){temp+=nums[i];crossLeft=max(crossLeft,temp);}// 从中点+1向右扫，找到最大和intcrossRight=nums[mid+1];temp=0;for(inti=mid+1;i<=right;i++){temp+=nums[i];crossRight=max(crossRight,temp);}intcrossSum=crossLeft+crossRight;// 返回三种情况的最大值returnmax(max(leftSum,rightSum),crossSum);}};

复杂度

复杂度分析总结

面试追问 FAQ

相关题目

总结

Kadane 算法是处理最大子数组和的标准解法，掌握后可以轻松解决环形子数组、乘积最大等变种问题。