你好，同学。欢迎参加 NOI 专题训练。

今天我们要挑战的是环形子数组最大和。这道题是经典“最大子序列和”问题（Kadane 算法）的进阶版。在 NOI 竞赛中，处理“环形结构”通常有两种思路：一、倍增数组线性化；二、利用总和减去反向极值。本题将带你深入理解第二种极具数学美感的思维方式。

---

一、 预备知识点

1. Kadane 算法：动态规划处理线性最大子数组和，时间复杂度 $O(N)$。
2. 动态规划（DP）：
   • max_sum[i]：以 $i$ 结尾的最大子数组和。
   • min_sum[i]：以 $i$ 结尾的最小子数组和。
3. 环形结构转换：理解环形最大和可能出现在数组中间，也可能跨越首尾。
4. 贡献法/正难则反：跨越首尾的最大子数组和 = 总和 - 内部最小子数组和。

---

二、 NOI 竞赛题目描述

题目名称：环形子数组最大和 (Maximum Sum Circular Subarray) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个长度为 $n$ 的环形整数数组 $A$，请你找出该数组的 非空 子数组的最大可能和。 环形数组意味着数组的末端与开头相连。对于子数组，每个元素最多只能出现一次。

【输入格式】 第一行包含一个整数 $n$。 第二行包含 $n$ 个整数，表示数组元素。

【输出格式】 输出一个整数，表示环形子数组的最大和。

【样例 1】 输入：

4
1 -2 3 -2

输出：

3

解释：从子数组 [3] 得到最大和 3。

【样例 2】 输入：

3
5 -3 5

输出：

10

解释：从子数组 [5, 5] 得到最大和 5 + 5 = 10。

【样例 3】 输入：

4
3 -2 2 -3

输出：

3

解释：从子数组 [3] 和 [3, -2, 2] 都可以得到最大和 3。

【数据规模与约定】

• $1 \le n \le 30,000$
• $-30,000 \le A[i] \le 30,000$

---

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们分情况讨论环形数组的特性。

1. 情况一：最大和不跨越首尾

• 现象：最大子数组就在数组中间，这与普通线性数组的最大子数组和完全一致。
• 工具：直接使用 Kadane 算法。
• 公式：currentMax = max(nums_i, currentMax + nums_i)

2. 情况二：最大和跨越首尾

• 观察：如果最大和跨越了首尾（即包含了开头一部分和结尾一部分），那么剩下的没被选中的部分，一定是中间一段连续的最小子数组和。
• 逆向思维：跨越首尾的最大和 = 数组总和 (Total) - 中间连续的最小子数组和 (MinSum)。
• 工具：同样使用 Kadane 逻辑求最小子数组和。

3. 边界细节：全负数

• 陷阱：如果数组全是负数（如 [-2, -3, -1]），Total - MinSum 会得到 0（相当于选了一个空数组），但题目要求“非空”。
• 对策：如果线性最大和 maxSum < 0，说明所有数都是负数，直接返回 maxSum。否则返回 max(maxSum, total - minSum)。

---

四、 算法流程图（伪代码逻辑）

graph TD
    Start(开始处理环形数组) --> Init(初始化 totalSum=0, maxS=-INF, curMax=0, minS=INF, curMin=0)
    Init --> Loop{遍历数组中的每个数 x}
    Loop -- 循环内部 --> UpdateTotal(totalSum 累加 x)
    UpdateTotal --> UpdateMax(curMax 等于 x 与 curMax加x 的较大者)
    UpdateMax --> GlobalMax(maxS 等于 maxS 与 curMax 的较大者)
    GlobalMax --> UpdateMin(curMin 等于 x 与 curMin加x 的较小者)
    UpdateMin --> GlobalMin(minS 等于 minS 与 curMin 的较小者)
    GlobalMin --> Loop
    Loop -- 遍历结束 --> CheckAllNeg{maxS 是否小于 0}
    CheckAllNeg -- 是 --> ResultA(输出 maxS)
    CheckAllNeg -- 否 --> ResultB(输出 maxS 与 totalSum减minS 的较大者)
    ResultA --> End(结束)
    ResultB --> End

---

五、 复杂度分析与优化建议

• 时间复杂度：$O(n)$。我们只需要对数组进行一次线性扫描，在循环内完成所有状态更新。
• 空间复杂度：$O(1)$。只需要常数个变量存储当前和及全局最值，不需要开辟额外的 DP 数组。

优化建议： 在 NOI 竞赛中，如果 $n$ 达到 $10^6$ 级别，要注意 total 的范围是否会超过 int（本题最大和约 $3 \times 10^4 \times 3 \times 10^4 = 9 \times 10^8$，在 int 范围内，但建议在累加时使用 long long 以防万一）。

---

六、 读题关键词总结

1. “环形” (Circular)：意味着需要考虑“跨越首尾”和“线性”两种情况。
2. “非空” (Non-empty)：提醒我们在处理“全负数”数组时，不能选择空集（总和减最小和可能误导致空集）。
3. “子数组” (Subarray)：说明元素必须是连续的，这是使用 Kadane 算法的前提。

在 OI 竞赛中，通过以下关键词快速识别 Kadane 的变体：

1. “连续子数组”：必须是连在一起的一段。
2. “最大和”：寻找最优累加结果。
3. “环形”：提示存在“首尾相连”或“总和减去中间最小段”的思路。
4. “非空”：特别提醒你在全负数数据下，不可选择空集导致结果为 0。

教练寄语： 处理环形问题的最高境界是“心中无环”。通过“总和减去最小区间”的转化，我们巧妙地把环形问题重新拉回到线性的逻辑中。这种“补集”思想在 NOI 组合数学和动态规划题目中非常高频。去实现它吧！