企业官网建设流程全解析

LeetCode 918这道环形子数组最大和，我刷题时绕了不少弯路。它和普通的最大子数组和（LeetCode 53）最大的区别就在“环形”两个字上：数组首尾相接，子数组可以偷偷跨过边界，把两边拼起来。如果你直接用53题的Kadane算法，大概率会漏掉这种情况。这篇文章我会把两种主流解法完整拆开讲：一种是“非跨边界和跨边界分类讨论”，另一种是“把数组复制一倍，配合前缀和与单调队列”。两种解法的时间复杂度都是O(n)，但思考角度完全不同，面试时能讲出任意一种都比背模板强。适合正在刷LeetCode热门100题、准备周赛，或者单纯想搞懂环形数组问题的读者。

1. 题目还原与两种解法的宏观选择

1.1 题目到底在考什么

先明确题目：给定一个长度为n的环形整数数组nums，返回非空子数组的最大可能和。这里“非空”很关键，意味着你不能为了规避负数就返回0，除非数组里本来就有空子数组作为合法答案。

环形数组意味着什么？我习惯把它理解成“数组最后一个元素后面又接上第一个元素”。比如nums = [5, -3, 5]，普通数组里的最大子数组和是[5, -3, 5]加起来等于7，但环形数组里可以取末尾的5和开头的5，中间隔着-3，跨过边界拼起来就是10。这就是本题的难点：你枚举的区间可能不是普通数组下标里连续的一段，而是在“下标循环”意义下连续的一段。

很多人的第一反应是枚举断点，把环在某处剪开变成线，然后跑Kadane。这个方向不是不行，但需要枚举n个断点，每个断点都跑一次求最大子数组和，总复杂度O(n^2)，n稍微大一点就超时。所以我们需要更聪明的办法：要么把环的两种情况合并成两个线性问题，要么直接把环“拉直”成一个带长度限制的线性数组。

1.2 为什么不能直接套普通Kadane算法

普通Kadane算法的核心是维护“以当前位置结尾的最大子数组和”，它天然假设区间在数组内部连续，不涉及循环。如果直接拿它跑一遍环形数组，得到的结果只能是“不跨越边界”的最大子数组和，跨边界的情况直接被忽略。

举一个典型例子：nums = [5, -3, 5]。普通Kadane从头到尾跑一遍，得到的是7，也就是整段都选。但正确答案是10，因为环形可以只选两端的5和5。这说明单靠普通Kadane覆盖不了所有情况。那怎么办？有两个思路：

• 思路一：按“是否跨越边界”分类。不跨越边界就用普通Kadane；跨越边界的那部分，等价于“数组总和 - 不跨越边界的最小子数组和”。因为跨越边界的子数组，从环上看其实就是把中间一段连续部分挖掉，挖得越少，剩下的越多。
• 思路二：不要急于处理环形，而是把原数组复制一份，拼成2n长度。任意一个环形子数组，都能在这个2n数组里找到一个普通连续段；再加上“子数组长度不能超过n”的限制，问题就变成了“在2n长的线性数组里，找长度不超过n的最大子数组和”。这类问题非常适合前缀和加单调队列。

这两个思路对应了下面的两种解法。提前理解全局，后面写代码时就不容易迷失。

1.3 两种解法的宏观对比

解法一的优点是代码短，只需要Kadane算法跑两遍，一遍找最大子数组和，一遍找最小子数组和，再做一次特判。缺点是那个特判（全负数时不能返回0）非常容易漏，很多人写出来发现样例有几个跑不过，就是因为忘了处理“最小子数组和等于整个数组和”的情况。

解法二更通用，它把环形问题转化成了“长度受限的最大子数组和”问题。以后你遇到类似“环形数组最大平均值”“环形数组最长连续子序列”等题目，都可以照搬复制数组加单调队列的思路。缺点是单调队列的边界条件比较多，队首什么时候弹、队尾怎么维护、窗口长度怎么限制，写错一个答案就莫名其妙。

我建议学的时候先把解法一吃透，因为它能帮你理解“总和减最小子段”这个核心trick；再上手解法二，因为它才是通吃环形连续子数组问题的通用武器。

2. 解法一：分类讨论，巧用 Kadane 双跑

2.1 核心推导：不跨边界和跨边界分开算

假设答案对应的环形子数组有两种可能：

• 第一种，它没有跨越原数组的边界，就是普通数组里的一段连续区间。这种情况直接用Kadane求最大子数组和maxSub。
• 第二种，它跨越了边界，也就是从数组尾部取一部分，再连接头部的一部分。此时如果你把整个数组看成一个环，这个子数组的补集恰好是中间一段连续区间。因为整个环的和total是固定的，要让选中的部分最大，等价于让补集最小。补集是一个连续子数组，所以这一种情况的最大值就是total - minSub，其中minSub是普通数组里的最小子数组和。

于是答案可以写成：

如果maxSub < 0，也就是数组里所有数都为负数，那么任何跨越边界的选法都会对应一个空补集，而“不选任何数”不是合法答案。此时直接返回maxSub，也就是选一个最大的负数。

否则返回max(maxSub, total - minSub)。

这里特别说明一下“补集为空”的问题。在全负数情况下，比如[-1, -2, -3]，total = -6，minSub = -6（因为整个数组都是最小子数组），total - minSub = 0，这表示选中了一个空集，子数组为空，显然不合法。为了避免这个坑，必须加maxSub < 0的分支。还有一种等价写法是：只有当total != minSub时才考虑total - minSub，但maxSub < 0更直观。

2.2 完整代码实现

下面是Python的实现，注释写在关键逻辑旁边：

from typing import List def maxSubarraySumCircular(nums: List[int]) -> int: # 第一次 Kadane：求普通最大子数组和 max_ending = max_sub = nums[0] # 第二次 Kadane：求普通最小子数组和 min_ending = min_sub = nums[0] total = nums[0] for i in range(1, len(nums)): num = nums[i] total += num # 最大子数组：要么从当前元素重新开始，要么延续之前的 max_ending = max(num, max_ending + num) max_sub = max(max_sub, max_ending) # 最小子数组：要么从当前元素重新开始，要么延续之前的 min_ending = min(num, min_ending + num) min_sub = min(min_sub, min_ending) # 如果最大子数组和都是负数，表示整个数组全是负数 if max_sub < 0: return max_sub return max(max_sub, total - min_sub)

这个代码里有个小细节：max_ending的更新公式max(num, max_ending + num)，本质上是“新开一段”和“接在前面一段”之间做选择。最小子数组同理，只是把max换成min。这段代码同时跑两个Kadane，一次遍历就搞定，空间复杂度O(1)。

2.3 手动演练两个例子

第一个例子：nums = [5, -3, 5]。

• total = 7
• 遍历过程：max_sub最终是7（[5, -3, 5]整体），min_sub最终是-3（单独选-3），total - min_sub = 7 - (-3) = 10。
• 返回max(7, 10) = 10。正确。

第二个例子：nums = [-1, -2, -3]。

• total = -6
• max_sub最终是-1（因为所有数都负，Kadane会不断选择当前元素，最大就是-1）
• min_sub最终是-6（整个数组）
• 如果直接max(-1, -6 - (-6)) = max(-1, 0) = 0，错误，因为空集不合法。
• 所以先判断max_sub < 0，返回-1。正确。

2.4 为什么“总和减最小子数组和”不会误伤正数数组

有读者会问：如果数组全是正数，比如[1, 2, 3]，minSub = 1（把1单独挖掉），total - minSub = 6 - 1 = 5，而maxSub = 6，最后取max(6, 5) = 6，没问题。这是否意味着这段逻辑多余？

不是多余，而是它覆盖了一个真实场景：数组里有正有负，但跨越边界的组合比内部任何连续段都大。比如[3, -2, 3]，内部最大是4（[3, -2, 3]整体），total = 4，minSub = -2，total - minSub = 6，对应跨边界选两端的3和3，答案是6。这时minSub是负数，补集确实被“挖掉”了，所以没有空集风险。

只有在所有数都为负数时，minSub才可能等于total，导致减出来是0。所以那个特殊分支不是可有可无，而是保证“子数组非空”的关键。

3. 解法二：复制数组 + 前缀和 + 单调队列

3.1 为什么复制数组能直接去掉环形

环形数组让人头疼的地方是“尾部接头部”不是线性关系。一个很自然的想法是：把原数组复制一份接在后面，得到一个长度2n的新数组。例如nums = [5, -3, 5]，拼接后变成[5, -3, 5, 5, -3, 5]。

这时候，原来环形数组里跨越边界的子数组[5] + [5]（也就是尾部5和头部5拼起来），在拼接数组里就是下标2和3的连续元素[5, 5]，对应拼接数组中的[5, 5]连续段，和是10。任意环形子数组，都能在拼接数组里找到一个普通连续段与之对应。

但要注意，如果允许随便取，那么拼接数组里可能会出现长度超过n的连续段，比如把整个2n数组全选了。环形子数组的长度最多是n，因为同一个元素不能重复取。所以问题变成：在2n长度的数组中，找所有满足长度不超过n的连续子数组，返回其中最大的和。这就是一个带长度限制的最大子数组和问题。

3.2 前缀和加单调队列的原理

带长度限制的最大子数组和，用前缀和特别好算。设P[i]表示拼接数组前i个元素的和，其中P[0] = 0。那么从下标j到下标i-1这段连续子数组的和就是P[i] - P[j]，这里j < i，并且长度i - j <= n。

为了让和尽量大，对于每个右端点i，我们要在左边允许的范围内找最小的P[j]。允许的j需要满足两个条件：

• j < i，因为区间不能为空。
• j >= i - n，因为长度不能超过n。

随着i向右移动，允许的j的范围也是一个滑动窗口，窗口右端是i-1，左端是i-n。我们要快速查询窗口内的最小值，这种场景就是单调队列的经典用法。单调队列维护的是P[j]值的候选下标，并且保证从队头到队尾对应的P[j]是递增的。因为队头始终是当前窗口内最小的前缀和，每次直接拿P[i]减去队头对应的P[j]就能得到一个候选答案。

这里要特别理解：队列存储的是下标，不是前缀和的值。因为弹出过期元素时，需要根据下标的范围判断；而比较大小的时候，才取P[que[tail]]这样的值。

3.3 单调队列维护的三个动作

首先是窗口左边界移动。每次i前进，新的j范围是[Math.max(0, i - n), i - 1]，所以所有小于i - n的下标都要从队头弹出。必须在计算答案前弹出，否则可能用到一个长度超过n的旧前缀，算出的结果就不合法了。

其次是查询答案。弹出过期元素后，队头就是当前窗口内最小前缀和下标，直接计算P[i] - P[que[0]]，更新答案。

然后是入队。为了保证队列的单调递增性质，从队尾开始，如果当前前缀和P[i]小于等于队尾元素对应的P值，那么队尾元素以后不可能再成为最小值，直接弹出。然后i入队。这一步用“小于等于”而不是“小于”，是为了在值相等时保留靠右的下标，因为靠右的下标存活时间更长，更晚过期，对后续窗口更有利。

我见过的很多错误都出在入队和查询的顺序上。如果你先入队再查询，可能会让i自己和自己相减，得到0，但区间不能为空，所以答案会偏小。正确顺序是：先弹出过期队头，再查询答案，最后入队。这样队头肯定不会包含刚入队的当前下标。

3.4 完整代码实现

from typing import List from collections import deque def maxSubarraySumCircular(nums: List[int]) -> int: n = len(nums) doubled = nums + nums # 前缀和，长度 2n + 1，P[0] = 0 P = [0] * (2 * n + 1) for i in range(2 * n): P[i + 1] = P[i] + doubled[i] ans = float('-inf') q = deque([0]) # 队列里放前缀和下标，初始放 P[0] for i in range(1, 2 * n + 1): # 1. 弹出窗口外的下标：长度不能超过 n while q and q[0] < i - n: q.popleft() # 2. 当前右端点 i 对应的最大和 ans = max(ans, P[i] - P[q[0]]) # 3. 当前下标入队，并维护单调递增 while q and P[q[-1]] >= P[i]: q.pop() q.append(i) return ans

这个写法里，遍历i的范围是1到2n。为什么不是到2n - 1？因为右端点对应的实际结束下标是i-1，最大到2n-1就已经覆盖拼接数组全部元素；但为了统一用前缀和，i取到2n时，P[2n]仍然存在，并且因为i - n = n，窗口左边界也在合理范围内，所以多算一次没问题。实测这样写最不容易越界。

3.5 手算一遍验证正确性

还是用nums = [5, -3, 5]。

doubled = [5, -3, 5, 5, -3, 5]，P = [0, 5, 2, 7, 12, 9, 14]，n = 3，ans一开始是负无穷。

• i=1：窗口j >= -2，q=[0]，ans=P[1]-P[0]=5，然后P[1]=5入队，q=[0,1]。
• i=2：窗口j >= -1，队头0有效，ans=min? ans=max(5, P[2]-P[0]=2)=5。P[2]=2，队尾P[1]=5大于2，弹出1，q=[0,2]。
• i=3：窗口j >= 0，队头0有效，ans=max(5, P[3]-P[0]=7)=7。P[3]=7入队，q=[0,2,3]。
• i=4：窗口j >= 1，队头0过期，弹出。队头2有效，ans=max(7, P[4]-P[2]=12-2=10)=10。P[4]=12入队，q=[2,3,4]。
• i=5：窗口j >= 2，队头2有效，ans=max(10, P[5]-P[2]=9-2=7)=10。P[5]=9，队尾P[4]=12大于9，弹出4，队尾P[3]=7小于9，入队，q=[2,3,5]。
• i=6：窗口j >= 3，队头2过期，弹出。队头3有效，ans=max(10, P[6]-P[3]=14-7=7)=10。

结果10，正确。这一步手动走完，单调队列的“弹头”“弹尾”就很清楚了。

4. 两种解法对比与适用场景

4.1 复杂度与代码量对比

从理论复杂度看，两种解法都是时间O(n)、空间O(n)吗？解法一空间O(1)，解法二因为拼接数组和前缀和需要O(n)空间。不过解法二的空间也能优化到O(n)以内，因为单调队列里最多n个下标，加上前缀和数组O(2n)，整体还是O(n)。

单就这道题而言，解法一更推荐在面试中快速写出。它代码量小，逻辑容易验证，只要解释清楚“为什么跨越边界等于总和减最小子数组”，面试官一般都会认可。解法二则适合作为进阶方案，尤其是当面试官追问“如果限制子数组长度不超过k，你会怎么做”，这时候解法一就没法直接改，解法二只需把窗口长度限制改成k即可。

4.2 从应试角度怎么选

如果你是为了刷LeetCode周赛或日常刷题，我建议先掌握解法一，因为它能让你在5分钟内写出一道中等题的AC代码。但千万不要只背代码，一定得能口述清楚：

• 普通最大子数组和为什么不覆盖跨边界；
• 跨边界为什么等于total - minSub；
• 为什么全负数时要单独返回maxSub。

解法二是对“环形连续子数组”这类问题更本质的理解。我把这个模板记住了以后，很多看似复杂的环形题都能转化成“窗口内最小前缀和”的套路。所以如果你是那种喜欢总结模型的人，解法二值得多花半小时吃透。

4.3 一个生活化的类比

解法一有点像你在环形跑道上跑步，想跑尽可能长的距离，但又不能跑重复路段。你可以选择不跨起点的跑法，直接找一段最长距离；也可以选择几乎跑完整圈，只跳过中间一段最短的障碍路段。跳过越短，剩下跑的距离越长。

解法二则像你把环形跑道拍平，铺成两条首尾相接的直道，然后要求你在任意连续的一段里跑，但最多只能跑一圈。这样环形跑道的所有路线都被包含进去了。

5. 常见问题与避坑指南

5.1 全负数数组为什么结果不是0

这是解法一最经典的坑。正常Kadane算普通最大子数组和，如果遇到[-1, -2, -3]，maxSub会变成-1。此时total - minSub = -6 - (-6) = 0。很多题解里为了不让返回0，直接写if maxSub < 0 return maxSub。这一步不能少。

如果你用解法二，因为拼接数组里窗口长度至少为1，队头永远不会是自己，加上窗口内有至少一个元素，所以不会出现选中空集的情况。这也是解法二写起来省心的原因之一。

5.2 单调队列的队头弹出条件写错

我见过有人把弹出条件写成while q and q[0] <= i - n，其实应该是<。窗口允许的j满足j >= i - n，所以当q[0] == i - n时，它仍然合法，不能弹。如果写成<=，就会多弹掉一个合法的最小值，导致答案偏小。

判断时可以用一个具体例子验证：窗口长度为n时，j等于i-n表示正好取满一个窗口，长度为n，必须保留。所以条件一定是q[0] < i - n。

5.3 前缀和数组长度到底开多少

解法二里，P数组长度是2n+1，因为前缀和需要多一个P[0]占位。遍历时i从1到2n，刚好能覆盖所有以拼接数组第2n-1个元素结尾的子数组。如果你写成range(1, 2n)，会漏掉最后一个后缀；如果写成range(2n+1)并把i=0也算进去，会造成空集问题。

这类边界问题，最简单的排查方法就是拿一个长度为1的数组去跑。比如nums=[5]，doubled=[5,5]，P=[0,5,10]，n=1。循环i=1时q=[0]，先弹队头（q[0]<0不弹），ans=P[1]-P[0]=5，然后入队1；i=2时，q[0]<1，弹出0，ans=P[2]-P[1]=5，答案还是5。这样能把边界验证清楚。

5.4 C++选手要注意的溢出问题

如果你用C++写这题，数组元素范围是-310^4到310^4，长度最多310^4，前缀和最大能到910^8，实际上不会超过int范围。但在其他变体题里，前缀和可能很大，建议直接用long long存前缀和和答案，避免溢出。不要因为LeetCode这题数据弱就忽略这一点，面试官可能会故意改几个大数考你。

5.5 把两个解法放到一起看

有时候解法一跑出来不对，不是因为Kadane写错，而是因为你没有把minSub和maxSub放在同一个循环里正确初始化。如果只初始化nums[0]没问题，但如果你把minSub初始化为0，就会导致最小子数组和始终是0或负数，最后结果乱掉。

我把容易出错的地方整理成一个速查表，刷题时可以直接对照：

最后再分享一个我自己的刷题体会：环形数组的题，第一次做时很容易被“环”这个词吓住，但本质上它只是在普通线性结构上加了一个“跨边界”的可能。解法一的核心是分类，解法二的核心是转化。把这两招都练熟，以后不管遇到环形数组、循环链表还是循环队列相关的算法题，脑子里都会自动浮现出“能不能断开”和“能不能复制拉直”两个方向。LeetCode 918这道题不大，但它串联起来的知识点却很值得反复琢磨。