题干与适用场景
输入长度为 n 的整数数组，数组首尾相连；连续子数组可以跨越尾部和首部，但不能重复使用同一位置。返回非空子数组的最大和。面试中常要求从普通 Kadane 算法推导环形变体，并解释全负数组为何不能直接用 total - minSum。
面试官考察点
- 能否把环形答案拆成“不跨边界”和“跨边界”两类。
- 能否用最大子数组和与最小子数组和的互补关系避免复制数组。
- 能否保留非空约束，处理全负数组、单元素和整数范围。
回答前需要澄清的问题
- 子数组是否必须非空？本题必须非空，因此全负数组要返回最大负数。
- 每个位置能否使用两次？不能；跨边界区间等价于删除一个非空中间区间。
- 只需要和还是还要返回起止位置？本题只返回和；若要位置，需要额外记录边界并处理跨界映射。
30 秒回答框架
我把答案分成两类：不跨边界时就是普通最大子数组和；跨边界时等于总和减去一个非空最小子数组和。一次扫描同时维护最大和、最小和与总和。如果最小子数组覆盖了整个数组，total - minSum 会代表空子数组，必须返回普通最大和。这样时间 O(n)、额外空间 O(1)。
分步骤深入解答
1. 推导两类答案
不跨边界的最优区间由 Kadane 算法得到。跨边界区间由数组后缀加前缀组成，它的补集是数组中间的一段非空连续区间，因此其和为 total - minSubarray。两类取最大值即可覆盖所有合法区间。
2. 维护 Kadane 不变量
扫描到元素 x 时，普通最大和维护“以当前位置结尾的最大和”；最小和维护“以当前位置结尾的最小和”。更新顺序可以是先用旧前缀计算新候选，再更新前缀极值。初始化时最大和为负无穷、最小和为正无穷，确保单元素负数组不会被当成空答案。
3. 处理全负数组
若所有元素为负，最小子数组就是整个数组，total - minSubarray = 0，这对应空区间，违反题意。此时直接返回普通 Kadane 的最大和。判断可以写成“最大和为负”，也可以在实现中记录最小区间是否覆盖全数组；前者更简洁。
4. 代码与复杂度
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))每个元素只访问一次，时间复杂度 O(n)，额外空间复杂度 O(1)。若整数范围可能超过语言的机器整数，total 和中间和要使用更宽类型。
5. 关键反例与验证
[5,-3,5] 的跨界答案是 5 + 5 = 10。[-3,-2,-3] 不能返回 0，必须返回 -2。[1,-2,3,-2] 的普通答案为 3，跨界候选不会超过它。测试还应覆盖一个元素、全正、首尾相连后等价于整段数组，以及最大数值相加接近整数上限。
高质量示范回答
“我先区分区间是否跨越尾首。不跨界就是 Kadane 的最大子数组和；跨界区间可以看成删除一段中间的非空最小子数组，所以候选是总和减最小和。我在一次遍历里同时维护最大和、最小和和总和。全负时最小区间会等于整个数组，补集变成空区间，因此直接返回普通最大和。这个实现每个元素访问一次，时间 O(n)、空间 O(1)，并用单元素和接近整数边界的用例检查非空约束和溢出。”
常见错误
- 复制数组后跑普通 Kadane → 可能重复使用同一位置 → 限制窗口长度或使用互补区间推导。
- 无条件返回
total - minSum→ 全负数组得到空区间 0 → 先处理最大和为负的分支。 - 把最小子数组允许为空 → 跨界公式失去非空补集约束 → 最小 Kadane 也必须从真实元素开始。
- 只给 O(n) 结论不解释不变量 → 无法证明边界覆盖完整 → 明确两类区间和每个状态的定义。
追问及应对
如果要求返回区间起止位置怎么办？
同时记录最大和与最小和的起止索引。跨界答案的区间是最小区间补集，可能表示为 [minEnd+1,n-1] 与 [0,minStart-1] 两段；需要规定返回两个区间还是映射成环上的起点和长度。
如果允许空子数组，代码如何改变？
最大答案至少为 0，初始化和转移可以允许当前和归零；但这改变了全负数组的语义。应先确认题意，再决定是否使用允许空区间的 Kadane。
如果数组是动态流，能否 O(1) 更新？
单端追加可以维护前缀、后缀和及相关摘要，但删除任意旧元素会破坏最小/最大区间信息，通常需要线段树或分块摘要。先明确更新方向、查询频率和是否允许近似，再选择数据结构。
如果要求恰好长度 k 呢？
互补公式不能直接套用，因为补集长度也被固定约束。可把数组视为长度 2n 的序列，用滑动窗口或前缀和维护长度为 k 的区间，并限制窗口不超过 n；复杂度与 k 和查询模式相关。