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