刷题路上遇到环形数组的问题总容易被“环形”这个条件绕晕——子数组不仅能是常规的连续片段还能跨数组首尾连接。今天就来拆解 LeetCode 918 题「环形子数组的最大和」分享两种高效解法从原理到代码一步步讲透帮你彻底搞懂这类环形数组问题。先看题目核心给定一个长度为 n 的环形整数数组 nums返回非空子数组的最大可能和。这里要注意两个关键约束一是环形意味着数组首尾相连二是子数组不能重复使用元素也就是说跨首尾的子数组比如 nums[n-1], nums[0], nums[1] 是允许的但不能包含 nums[0] 两次。题目核心难点常规的子数组最大和比如 LeetCode 53 题用 Kadane 算法就能轻松解决但环形数组多了“跨首尾”的情况这就需要我们跳出常规思维常规子数组从 i 到 ji ≤ j连续且不跨首尾环形子数组从 j 到 n-1再从 0 到 ij i本质是“数组总和 - 中间一段最小子数组的和”。基于这个思路衍生出两种经典解法下面分别详细讲解。解法一全局最大值 max(常规最大和, 总和 - 常规最小和)核心原理这是最直观、最易理解的解法核心逻辑分两种情况最大子数组不跨首尾就是常规的子数组最大和用 Kadane 算法直接求解最大子数组跨首尾此时最大和 数组总和 - 最小子数组的和因为总和减去中间一段最小的子数组剩下的就是跨首尾的最大子数组。还有一个特殊情况如果数组中所有元素都是负数那么“总和 - 最小子数组和”会得到 0因为总和 最小子数组和但题目要求子数组非空所以此时直接返回常规最大和即数组中最大的那个负数。代码解析TypeScriptfunctionmaxSubarraySumCircular_1(nums:number[]):number{if(nums.length0)return0;letcurMaxnums[0],maxSumnums[0];// 常规最大和相关letcurMinnums[0],minSumnums[0];// 常规最小和相关lettotalSumnums[0];// 数组总和for(leti1;inums.length;i){// 常规Kadane算法求最大子数组和curMaxMath.max(nums[i],curMaxnums[i]);maxSumMath.max(maxSum,curMax);// 同理求最小子数组和Kadane算法变种curMinMath.min(nums[i],curMinnums[i]);minSumMath.min(minSum,curMin);// 累加计算数组总和totalSumnums[i];}// 特殊情况所有元素都是负数直接返回最大和非空if(maxSum0){returnmaxSum;}// 两种情况取最大值常规最大和 vs 总和 - 最小子数组和returnMath.max(maxSum,totalSum-minSum);};关键细节curMax 和 curMin 分别记录“以当前元素结尾的最大子数组和”和“以当前元素结尾的最小子数组和”每次迭代更新totalSum 必须在迭代中累加避免二次遍历数组保证时间复杂度 O(n)判断 maxSum 0 是核心容错避免所有元素为负时返回 0不符合非空子数组要求。解法二前缀和 后缀枚举避免总和为负的判断核心原理这种解法的思路是“拆分环形子数组”跨首尾的子数组可以拆分为「前缀子数组」从 0 开始和「后缀子数组」到 n-1 结束。我们可以先计算常规的最大子数组和不跨首尾再计算“后缀子数组 前缀子数组”的最大和用 leftMax 数组记录「从 0 到 i 的最大前缀和」再从右到左枚举后缀子数组每次将后缀和与 leftMax[i-1]前 i-1 个元素的最大前缀和相加取最大值。这种方法不需要判断数组是否全为负因为枚举的后缀和 前缀和都是非空的且常规最大和已经覆盖了全负的情况。代码解析TypeScriptfunctionmaxSubarraySumCircular_2(nums:number[]):number{letn:numbernums.length;// leftMax[i]从0开始到i为止的最大前缀和必须包含0保证前缀非空constleftMaxnewArray(n).fill(0);leftMax[0]nums[0];// 初始值只有第一个元素的前缀和letleftSum:numbernums[0];// 累加前缀和letpre:numbernums[0];// 常规最大子数组和的中间变量Kadaneletres:numbernums[0];// 最终结果初始化为第一个元素// 第一次遍历计算常规最大和 leftMax数组for(leti1;in;i){// 常规Kadane算法求最大子数组和preMath.max(prenums[i],nums[i]);resMath.max(res,pre);// 累加前缀和更新leftMax保证leftMax[i]是0到i的最大前缀和leftSumnums[i];leftMax[i]Math.max(leftMax[i-1],leftSum);}// 第二次遍历从右到左枚举后缀子数组计算后缀和 对应最大前缀和letrightSum0;for(letin-1;i0;i--){rightSumnums[i];// 后缀和从i到n-1的和// 后缀和i到n-1 前缀和0到i-1的最大更新结果resMath.max(res,rightSumleftMax[i-1]);}returnres;};关键细节leftMax 数组的核心作用记录“以 0 为起点到 i 为止”的最大前缀和确保后续枚举后缀时能快速找到对应的最大前缀第二次遍历从 n-1 到 1不包含 0因为当 i0 时leftMax[i-1] 越界且此时后缀和就是整个数组已经被常规最大和覆盖时间复杂度依然是 O(n)空间复杂度 O(n)leftMax 数组相比解法一多了一点空间但避免了总和为负的判断逻辑更简洁。两种解法对比解法时间复杂度空间复杂度核心优势适用场景解法一总和 - 最小和O(n)O(1)空间最优逻辑直观追求空间效率能记住“全负判断”的场景解法二前缀后缀O(n)O(n)无需特殊判断逻辑更简洁不想处理边界条件追求代码简洁刷题总结环形子数组的最大和本质是“常规子数组”和“跨首尾子数组”的最大值求解。两种解法都基于 Kadane 算法的延伸核心是找到“跨首尾子数组”的等价转换方式——要么用总和减去最小子数组和要么拆分为前缀后缀。刷题时可以根据自己的习惯选择如果喜欢空间最优优先解法一如果怕遗漏边界条件解法二更友好。另外建议多动手模拟几个测试用例比如全负数组、全正数组、混合数组就能彻底掌握两种解法的逻辑。
LeetCode 918. 环形子数组的最大和：两种解法详解
刷题路上遇到环形数组的问题总容易被“环形”这个条件绕晕——子数组不仅能是常规的连续片段还能跨数组首尾连接。今天就来拆解 LeetCode 918 题「环形子数组的最大和」分享两种高效解法从原理到代码一步步讲透帮你彻底搞懂这类环形数组问题。先看题目核心给定一个长度为 n 的环形整数数组 nums返回非空子数组的最大可能和。这里要注意两个关键约束一是环形意味着数组首尾相连二是子数组不能重复使用元素也就是说跨首尾的子数组比如 nums[n-1], nums[0], nums[1] 是允许的但不能包含 nums[0] 两次。题目核心难点常规的子数组最大和比如 LeetCode 53 题用 Kadane 算法就能轻松解决但环形数组多了“跨首尾”的情况这就需要我们跳出常规思维常规子数组从 i 到 ji ≤ j连续且不跨首尾环形子数组从 j 到 n-1再从 0 到 ij i本质是“数组总和 - 中间一段最小子数组的和”。基于这个思路衍生出两种经典解法下面分别详细讲解。解法一全局最大值 max(常规最大和, 总和 - 常规最小和)核心原理这是最直观、最易理解的解法核心逻辑分两种情况最大子数组不跨首尾就是常规的子数组最大和用 Kadane 算法直接求解最大子数组跨首尾此时最大和 数组总和 - 最小子数组的和因为总和减去中间一段最小的子数组剩下的就是跨首尾的最大子数组。还有一个特殊情况如果数组中所有元素都是负数那么“总和 - 最小子数组和”会得到 0因为总和 最小子数组和但题目要求子数组非空所以此时直接返回常规最大和即数组中最大的那个负数。代码解析TypeScriptfunctionmaxSubarraySumCircular_1(nums:number[]):number{if(nums.length0)return0;letcurMaxnums[0],maxSumnums[0];// 常规最大和相关letcurMinnums[0],minSumnums[0];// 常规最小和相关lettotalSumnums[0];// 数组总和for(leti1;inums.length;i){// 常规Kadane算法求最大子数组和curMaxMath.max(nums[i],curMaxnums[i]);maxSumMath.max(maxSum,curMax);// 同理求最小子数组和Kadane算法变种curMinMath.min(nums[i],curMinnums[i]);minSumMath.min(minSum,curMin);// 累加计算数组总和totalSumnums[i];}// 特殊情况所有元素都是负数直接返回最大和非空if(maxSum0){returnmaxSum;}// 两种情况取最大值常规最大和 vs 总和 - 最小子数组和returnMath.max(maxSum,totalSum-minSum);};关键细节curMax 和 curMin 分别记录“以当前元素结尾的最大子数组和”和“以当前元素结尾的最小子数组和”每次迭代更新totalSum 必须在迭代中累加避免二次遍历数组保证时间复杂度 O(n)判断 maxSum 0 是核心容错避免所有元素为负时返回 0不符合非空子数组要求。解法二前缀和 后缀枚举避免总和为负的判断核心原理这种解法的思路是“拆分环形子数组”跨首尾的子数组可以拆分为「前缀子数组」从 0 开始和「后缀子数组」到 n-1 结束。我们可以先计算常规的最大子数组和不跨首尾再计算“后缀子数组 前缀子数组”的最大和用 leftMax 数组记录「从 0 到 i 的最大前缀和」再从右到左枚举后缀子数组每次将后缀和与 leftMax[i-1]前 i-1 个元素的最大前缀和相加取最大值。这种方法不需要判断数组是否全为负因为枚举的后缀和 前缀和都是非空的且常规最大和已经覆盖了全负的情况。代码解析TypeScriptfunctionmaxSubarraySumCircular_2(nums:number[]):number{letn:numbernums.length;// leftMax[i]从0开始到i为止的最大前缀和必须包含0保证前缀非空constleftMaxnewArray(n).fill(0);leftMax[0]nums[0];// 初始值只有第一个元素的前缀和letleftSum:numbernums[0];// 累加前缀和letpre:numbernums[0];// 常规最大子数组和的中间变量Kadaneletres:numbernums[0];// 最终结果初始化为第一个元素// 第一次遍历计算常规最大和 leftMax数组for(leti1;in;i){// 常规Kadane算法求最大子数组和preMath.max(prenums[i],nums[i]);resMath.max(res,pre);// 累加前缀和更新leftMax保证leftMax[i]是0到i的最大前缀和leftSumnums[i];leftMax[i]Math.max(leftMax[i-1],leftSum);}// 第二次遍历从右到左枚举后缀子数组计算后缀和 对应最大前缀和letrightSum0;for(letin-1;i0;i--){rightSumnums[i];// 后缀和从i到n-1的和// 后缀和i到n-1 前缀和0到i-1的最大更新结果resMath.max(res,rightSumleftMax[i-1]);}returnres;};关键细节leftMax 数组的核心作用记录“以 0 为起点到 i 为止”的最大前缀和确保后续枚举后缀时能快速找到对应的最大前缀第二次遍历从 n-1 到 1不包含 0因为当 i0 时leftMax[i-1] 越界且此时后缀和就是整个数组已经被常规最大和覆盖时间复杂度依然是 O(n)空间复杂度 O(n)leftMax 数组相比解法一多了一点空间但避免了总和为负的判断逻辑更简洁。两种解法对比解法时间复杂度空间复杂度核心优势适用场景解法一总和 - 最小和O(n)O(1)空间最优逻辑直观追求空间效率能记住“全负判断”的场景解法二前缀后缀O(n)O(n)无需特殊判断逻辑更简洁不想处理边界条件追求代码简洁刷题总结环形子数组的最大和本质是“常规子数组”和“跨首尾子数组”的最大值求解。两种解法都基于 Kadane 算法的延伸核心是找到“跨首尾子数组”的等价转换方式——要么用总和减去最小子数组和要么拆分为前缀后缀。刷题时可以根据自己的习惯选择如果喜欢空间最优优先解法一如果怕遗漏边界条件解法二更友好。另外建议多动手模拟几个测试用例比如全负数组、全正数组、混合数组就能彻底掌握两种解法的逻辑。
