1. 题目
题目链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
LeetCode 918 环形子数组最大和：给一个环形整数数组 nums，求最大的非空子数组和。环形的意思是最后一个元素的下一个元素是第一个元素，子数组可以从尾部绕回头部继续取，但每个位置最多只能被取一次。
普通的最大子数组和是个扫一遍就完事，从左到右维护「以当前位置结尾的最大和」，贪心地决定要不要丢掉前面那段，O(n) 结束。环形版本的麻烦在跨界区间：合法答案可能是从下标 n-2 开始，走到 n-1，再绕回 0、1。这种区间在线性数组上根本不连续，一次从左到右的扫描抓不到它。
nums = [5,-3,5]，答案是 10。取法是最后一个 5 加上第一个 5，跨过中间的 -3 绕了回来。所有不跨界的连续子数组里最大的只有 7，够不着。
2. 破环成链
处理环最直接的办法：把数组复制一份接在自己后面，得到长度 2n 的线性数组。
[5,-3,5] → [5,-3,5,5,-3,5]原数组里那个跨界的「下标 2 绕回下标 0」，在展开数组里就是下标 2 到 3 这段连续区间 [5,5]，和还是 10。
关键结论是：原数组里任何一个环形子数组（长度 ≤ n），在展开数组里都能找到一段长度不超过 n 的连续子数组与之对应；反过来，展开数组里任意一段长度 ≤ n 的连续子数组，按下标映射回原数组也一定是合法的环形子数组。长度限制：只允许取到 n+1，超出了则意味着原数组某个元素被用了两次。
于是问题转化为：在长度 2n 的数组上，求所有长度不超过 n 的子数组的最大和。
3. 前缀和：把区间和变成两点差
定义 prefixSum[k] 为前 k 个元素之和，prefixSum[0] = 0。那么区间 (i, j] 的和就是 prefixSum[j] - prefixSum[i]。
问题变成：找一对 i < j 且 j - i ≤ n，使 prefixSum[j] - prefixSum[i] 最大。
固定右端点 j 来看。prefixSum[j] 此时是定值，要让差值最大，就得让 prefixSum[i] 尽可能小；同时 i 必须落在 j 左侧、距离不超过 n 的窗口内。
再提炼一下：对每个 j，在它左侧长度为 n 的窗口里找最小的 prefixSum[i]。 最终转为滑动窗口最小值问题（单调队列的经典场景）。
4. 单调队列模板
滑动窗口最小值的通用写法，队列里存下标，对应的值从队首到队尾单调递增。每轮三个动作：
Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < arr.length; i++) { // 1. 过期弹出：队首下标滑出窗口就扔掉 while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize) { deque.pollFirst(); } // 2. 取最小值：队列单调递增，队首即当前窗口最小值，O(1) if (!deque.isEmpty()) { int min = arr[deque.peekFirst()]; } // 3. 入队维护单调性：弹掉队尾所有 >= 当前值的元素，再放入 while (!deque.isEmpty() && arr[deque.peekLast()] >= arr[i]) { deque.pollLast(); } deque.addLast(i);}5. 代码详解
class Solution { public int maxSubarraySumCircular(int[] nums) { // 展开数组长 2n，前缀和多留一位哨兵：prefixSum[0] = 0 int[] prefixSum = new int[nums.length * 2 + 1]; // 第一段：原数组的正常前缀和，填 [1, n] for (int i = 1; i <= nums.length; i++) { prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; } // 第二段：填 [n+1, 2n]，元素回绕取 nums[i - n - 1] 继续累加 for (int i = nums.length + 1; i <= nums.length * 2; i++) { prefixSum[i] = prefixSum[i - 1] + nums[i - nums.length - 1]; } int ans = nums[0]; // 兜底答案，见下文 Deque<Integer> deque = new ArrayDeque<>(); // 存下标，对应前缀和递增 for (int i = 1; i < prefixSum.length; i++) { // 操作1 过期弹出：左端点离 i 超过 n，子数组就超长了 while (!deque.isEmpty() && deque.peekFirst() < i - nums.length) { deque.pollFirst(); } // 操作2 更新答案：当前前缀和减窗口内最小前缀和 // 放在入队之前，保证队里全是严格小于 i 的下标 if (!deque.isEmpty()) { ans = Math.max(ans, prefixSum[i] - prefixSum[deque.peekFirst()]); } // 操作3 入队：弹掉队尾所有不小于当前值的，维护单调递增 while (!deque.isEmpty() && prefixSum[deque.peekLast()] >= prefixSum[i]) { deque.pollLast(); } deque.addLast(i); } return ans; }}前缀和两段构建：
- 第一段：套用模板。
- 第二段：
nums[i - nums.length - 1]是把下标映射回原数组：i 走到 n+1 时取nums[0]，走到 2n 时取nums[n-1]，正好把原数组又走了一遍。效果等价于先拼出 2n 长的数组再求前缀和，但省掉了拼接那一步和那块内存，也不用写取模。
ans 初始化为 nums[0]。 这是全负数场景的兜底。像 [-3,-2,-3] 这种输入，答案不能是 0 —— 0 对应空子数组，题目要求非空；而单调队列的更新逻辑在某些边界下未必能自然覆盖到「答案就是单个最大元素」的情况。拿 nums[0] 打底，保证 ans 从一开始就是一个合法子数组的和。
答案计算放在入队之前。 顺序很关键，如果先把 i 入队再取队首，队首完全可能就是 i 自己，算出 prefixSum[i] - prefixSum[i] = 0，对应长度为 0 的空子数组，非法。先算后入队，队里全是 < i 的下标，i < j 严格成立。
窗口大小取 n。 判断条件 deque.peekFirst() < i - nums.length 只保留下标落在 [i-n, i-1] 的左端点。区间 (left, i] 的长度是 i - left，最大取到 n，正好符合第 2 节那条「子数组长度不超过 n」的约束，不会出现某个元素被用两次。
6. 复杂度
时间 O(n)。前缀和两段构建共 2n 次赋值；主循环跑 2n 轮，内层虽有两个 while，但每个下标最多入队一次、出队一次，总操作次数是线性的，摊还到每轮是常数。
空间 O(n)。前缀和数组 2n+1 个 int；单调队列最坏情况下（前缀和严格递增，谁也弹不掉谁）存接近 n 个下标。
7. 总结
破环成链把环形降成线性，前缀和把区间和降成两点差，单调队列把窗口最小值降成 O(n)。
本文由 AgentPlanFlow 生成