LeetCode经典题目「53. 最大子数组和」这道题是动态规划和分治思想的典型应用也是面试中高频考察的基础题。题目难度不算高但两种解法各有侧重吃透能帮我们更好地理解两类算法的核心逻辑话不多说直接进入正题。一、题目回顾题目要求给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。注意子数组是数组中的一个连续部分和子序列不要求连续是完全不同的概念哦。举个简单例子输入 nums [-2,1,-3,4,-1,2,1,-5,4]输出应该是 6。因为连续子数组 [4,-1,2,1] 的和最大等于6。这道题的核心难点在于「连续」和「最大和」如果暴力枚举所有连续子数组时间复杂度会达到 O(n²)对于大规模数组会超时所以我们需要更高效的解法——今天重点讲两种 O(n) 和 O(nlogn) 复杂度的解法。二、解法一动态规划DP—— 最优时间复杂度 O(n)1. 核心思路动态规划的核心是「状态定义」和「状态转移方程」这道题我们可以这样拆解定义状态 pre表示以当前元素结尾的连续子数组的最大和。对于每个元素 nums[i]我们有两个选择将当前元素加入到之前的连续子数组中即 pre nums[i]放弃之前的子数组以当前元素为起点重新开始一个子数组即 nums[i]。所以状态转移方程就是pre Math.max(pre x, x)x 是当前遍历到的元素。同时我们需要一个变量 maxAns 来记录遍历过程中出现的最大 pre 值这个值就是最终的最大子数组和。2. 代码解读给出的代码非常简洁我们逐行拆解functionmaxSubArray_1(nums:number[]):number{// pre以当前元素结尾的连续子数组最大和maxAns全局最大和letpre:number0,maxAns:numbernums[0];// 遍历数组中的每个元素xnums.forEach((x){// 状态转移选择加入前序子数组或重新开始preMath.max(prex,x);// 更新全局最大和maxAnsMath.max(maxAns,pre);});returnmaxAns;};举个例子辅助理解以 nums [-2,1,-3,4,-1,2,1,-5,4] 为例初始pre0maxAns-2nums[0]遍历x-2pre max(0(-2), -2) -2maxAns max(-2, -2) -2遍历x1pre max(-21, 1) 1maxAns max(-2, 1) 1遍历x-3pre max(1(-3), -3) -2maxAns 仍为1遍历x4pre max(-24, 4) 4maxAns 4后续遍历依次更新最终 maxAns 为6和预期一致。这种解法的优势的是一次遍历完成时间复杂度 O(n)空间复杂度 O(1)只用到两个变量是这道题的最优解法面试中优先推荐写这种。三、解法二分治思想 —— 时间复杂度 O(nlogn)分治思想的核心是「分而治之」将数组分成左右两部分最大子数组和要么在左半部分要么在右半部分要么横跨左右两部分。我们需要分别计算这三种情况的最大值取三者中的最大者。1. 核心思路为了高效计算「横跨左右两部分」的最大和我们需要定义一个 Status 类存储每个区间的四个关键信息lSum该区间的最大前缀和从区间左端点开始连续子数组的最大和rSum该区间的最大后缀和从区间右端点开始连续子数组的最大和mSum该区间的最大子数组和就是我们需要的核心值iSum该区间的所有元素和用于计算横跨左右的最大和。然后通过「递归拆分」和「合并区间」pushUp 函数逐步计算出整个数组的 mSum即为答案。2. 代码解读classStatus{lSum:number;// 区间最大前缀和rSum:number;// 区间最大后缀和mSum:number;// 区间最大子数组和iSum:number;// 区间总元素和constructor(l:number,r:number,m:number,i:number){this.lSuml;this.rSumr;this.mSumm;this.iSumi;}}functionmaxSubArray_2(nums:number[]):number{// 合并两个区间的Status计算出父区间的四个关键值constpushUp(l:Status,r:Status):Status{constiSuml.iSumr.iSum;// 父区间总和 左区间总和 右区间总和// 父区间最大前缀和要么是左区间的最大前缀和要么是左区间总和右区间最大前缀和constlSumMath.max(l.lSum,l.iSumr.lSum);// 父区间最大后缀和要么是右区间的最大后缀和要么是右区间总和左区间最大后缀和constrSumMath.max(r.rSum,r.iSuml.rSum);// 父区间最大子数组和三者取最大左区间最大、右区间最大、横跨左右的最大constmSumMath.max(Math.max(l.mSum,r.mSum),l.rSumr.lSum);returnnewStatus(lSum,rSum,mSum,iSum);}// 递归获取区间 [l, r] 的StatusconstgetInfo(a:number[],l:number,r:number):Status{if(lr){// 递归终止区间只有一个元素时四个值都等于该元素returnnewStatus(a[l],a[l],a[l],a[l]);}constmMath.floor((lr)/2);// 拆分区间为左右两部分constlSubgetInfo(a,l,m);// 左区间StatusconstrSubgetInfo(a,m1,r);// 右区间StatusreturnpushUp(lSub,rSub);// 合并左右区间返回父区间Status}// 整个数组的区间是 [0, nums.length-1]其mSum就是答案returngetInfo(nums,0,nums.length-1).mSum;};3. 补充说明分治解法的时间复杂度是 O(nlogn)空间复杂度是 O(logn)递归调用栈的深度。虽然效率不如动态规划但这种思想很重要——在解决更复杂的区间问题如最大子矩阵和时分治区间信息合并的思路会非常有用。四、两种解法对比总结解法时间复杂度空间复杂度核心优势适用场景动态规划O(n)O(1)高效、简洁空间开销小单独求解最大子数组和面试首选分治思想O(nlogn)O(logn)思路通用可扩展到复杂区间问题区间相关延伸题理解分治思想五、刷题思考这道题虽然简单但能帮我们理清两个重要算法思想的应用动态规划的核心是「抓住当前状态的最优选择」不需要回溯通过状态转移逐步推导全局最优分治思想的核心是「拆分合并」将大问题拆成小问题解决再通过合并小问题的结果得到大问题的答案。
LeetCode 53. 最大子数组和：两种高效解法（动态规划+分治）
LeetCode经典题目「53. 最大子数组和」这道题是动态规划和分治思想的典型应用也是面试中高频考察的基础题。题目难度不算高但两种解法各有侧重吃透能帮我们更好地理解两类算法的核心逻辑话不多说直接进入正题。一、题目回顾题目要求给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。注意子数组是数组中的一个连续部分和子序列不要求连续是完全不同的概念哦。举个简单例子输入 nums [-2,1,-3,4,-1,2,1,-5,4]输出应该是 6。因为连续子数组 [4,-1,2,1] 的和最大等于6。这道题的核心难点在于「连续」和「最大和」如果暴力枚举所有连续子数组时间复杂度会达到 O(n²)对于大规模数组会超时所以我们需要更高效的解法——今天重点讲两种 O(n) 和 O(nlogn) 复杂度的解法。二、解法一动态规划DP—— 最优时间复杂度 O(n)1. 核心思路动态规划的核心是「状态定义」和「状态转移方程」这道题我们可以这样拆解定义状态 pre表示以当前元素结尾的连续子数组的最大和。对于每个元素 nums[i]我们有两个选择将当前元素加入到之前的连续子数组中即 pre nums[i]放弃之前的子数组以当前元素为起点重新开始一个子数组即 nums[i]。所以状态转移方程就是pre Math.max(pre x, x)x 是当前遍历到的元素。同时我们需要一个变量 maxAns 来记录遍历过程中出现的最大 pre 值这个值就是最终的最大子数组和。2. 代码解读给出的代码非常简洁我们逐行拆解functionmaxSubArray_1(nums:number[]):number{// pre以当前元素结尾的连续子数组最大和maxAns全局最大和letpre:number0,maxAns:numbernums[0];// 遍历数组中的每个元素xnums.forEach((x){// 状态转移选择加入前序子数组或重新开始preMath.max(prex,x);// 更新全局最大和maxAnsMath.max(maxAns,pre);});returnmaxAns;};举个例子辅助理解以 nums [-2,1,-3,4,-1,2,1,-5,4] 为例初始pre0maxAns-2nums[0]遍历x-2pre max(0(-2), -2) -2maxAns max(-2, -2) -2遍历x1pre max(-21, 1) 1maxAns max(-2, 1) 1遍历x-3pre max(1(-3), -3) -2maxAns 仍为1遍历x4pre max(-24, 4) 4maxAns 4后续遍历依次更新最终 maxAns 为6和预期一致。这种解法的优势的是一次遍历完成时间复杂度 O(n)空间复杂度 O(1)只用到两个变量是这道题的最优解法面试中优先推荐写这种。三、解法二分治思想 —— 时间复杂度 O(nlogn)分治思想的核心是「分而治之」将数组分成左右两部分最大子数组和要么在左半部分要么在右半部分要么横跨左右两部分。我们需要分别计算这三种情况的最大值取三者中的最大者。1. 核心思路为了高效计算「横跨左右两部分」的最大和我们需要定义一个 Status 类存储每个区间的四个关键信息lSum该区间的最大前缀和从区间左端点开始连续子数组的最大和rSum该区间的最大后缀和从区间右端点开始连续子数组的最大和mSum该区间的最大子数组和就是我们需要的核心值iSum该区间的所有元素和用于计算横跨左右的最大和。然后通过「递归拆分」和「合并区间」pushUp 函数逐步计算出整个数组的 mSum即为答案。2. 代码解读classStatus{lSum:number;// 区间最大前缀和rSum:number;// 区间最大后缀和mSum:number;// 区间最大子数组和iSum:number;// 区间总元素和constructor(l:number,r:number,m:number,i:number){this.lSuml;this.rSumr;this.mSumm;this.iSumi;}}functionmaxSubArray_2(nums:number[]):number{// 合并两个区间的Status计算出父区间的四个关键值constpushUp(l:Status,r:Status):Status{constiSuml.iSumr.iSum;// 父区间总和 左区间总和 右区间总和// 父区间最大前缀和要么是左区间的最大前缀和要么是左区间总和右区间最大前缀和constlSumMath.max(l.lSum,l.iSumr.lSum);// 父区间最大后缀和要么是右区间的最大后缀和要么是右区间总和左区间最大后缀和constrSumMath.max(r.rSum,r.iSuml.rSum);// 父区间最大子数组和三者取最大左区间最大、右区间最大、横跨左右的最大constmSumMath.max(Math.max(l.mSum,r.mSum),l.rSumr.lSum);returnnewStatus(lSum,rSum,mSum,iSum);}// 递归获取区间 [l, r] 的StatusconstgetInfo(a:number[],l:number,r:number):Status{if(lr){// 递归终止区间只有一个元素时四个值都等于该元素returnnewStatus(a[l],a[l],a[l],a[l]);}constmMath.floor((lr)/2);// 拆分区间为左右两部分constlSubgetInfo(a,l,m);// 左区间StatusconstrSubgetInfo(a,m1,r);// 右区间StatusreturnpushUp(lSub,rSub);// 合并左右区间返回父区间Status}// 整个数组的区间是 [0, nums.length-1]其mSum就是答案returngetInfo(nums,0,nums.length-1).mSum;};3. 补充说明分治解法的时间复杂度是 O(nlogn)空间复杂度是 O(logn)递归调用栈的深度。虽然效率不如动态规划但这种思想很重要——在解决更复杂的区间问题如最大子矩阵和时分治区间信息合并的思路会非常有用。四、两种解法对比总结解法时间复杂度空间复杂度核心优势适用场景动态规划O(n)O(1)高效、简洁空间开销小单独求解最大子数组和面试首选分治思想O(nlogn)O(logn)思路通用可扩展到复杂区间问题区间相关延伸题理解分治思想五、刷题思考这道题虽然简单但能帮我们理清两个重要算法思想的应用动态规划的核心是「抓住当前状态的最优选择」不需要回溯通过状态转移逐步推导全局最优分治思想的核心是「拆分合并」将大问题拆成小问题解决再通过合并小问题的结果得到大问题的答案。
