918. 环形子数组的最大和
题目描述
输入一个长度为 n 的整数数组 nums，把它看成首尾相接的环：nums[n-1] 之后紧跟 nums[0]。
在环上取一段连续、非空的元素，称为子数组。子数组可以跨过末尾绕回开头，但同一个位置的元素最多只能出现一次，因此长度不超过 n。
返回所有这样的子数组中元素和的最大值。
示例 1
输入：nums = [1,-2,3,-2] 输出：3
解释：只取 [3]，和为 3。
示例 2
输入：nums = [5,-3,5] 输出：10
解释：从末尾的 5 绕回开头的 5，得到 [5,5]，和为 10。
示例 3
输入：nums = [3,-2,2,-3] 输出：3
解释：[3] 或 [3,-2,2] 的和都是 3，没有更大的。
数据范围
n == nums.length1 <= n <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4
解题思路：Kadane 最大和与最小和
最大子数组只有两种形状：不跨边界时就是普通的最大子数组和（Kadane：cur = max(cur + x, x)）；跨边界时是“头一段 + 尾一段”，剩下的中间部分是一个普通子数组，要让头尾最大就要让中间最小，即 total - 最小子数组和。一遍扫描同时求最大和最小子数组和，取两者较大值。
为什么正确
处理完 x 后，cur_max / cur_min 是以 x 结尾的子数组最大 / 最小和，best_max / best_min 是目前已见的最大 / 最小子数组和。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
全是负数时最小子数组就是整个数组，total - best_min = 0 对应空子数组，不合法。所以 best_max < 0 时直接返回 best_max。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
cur_max, best_max = 0, nums[0]
cur_min, best_min = 0, nums[0]
for x in nums:
total += x
cur_max = max(cur_max + x, x)
best_max = max(best_max, cur_max)
cur_min = min(cur_min + x, x)
best_min = min(best_min, cur_min)
if best_max < 0:
return best_max
return max(best_max, total - best_min)class Solution {
public int maxSubarraySumCircular(int[] nums) {
int total = 0;
int curMax = 0, bestMax = nums[0];
int curMin = 0, bestMin = nums[0];
for (int x : nums) {
total += x;
curMax = Math.max(curMax + x, x);
bestMax = Math.max(bestMax, curMax);
curMin = Math.min(curMin + x, x);
bestMin = Math.min(bestMin, curMin);
}
if (bestMax < 0) {
return bestMax;
}
return Math.max(bestMax, total - bestMin);
}
}class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int total = 0;
int cur_max = 0, best_max = nums[0];
int cur_min = 0, best_min = nums[0];
for (int x : nums) {
total += x;
cur_max = max(cur_max + x, x);
best_max = max(best_max, cur_max);
cur_min = min(cur_min + x, x);
best_min = min(best_min, cur_min);
}
if (best_max < 0) {
return best_max;
}
return max(best_max, total - best_min);
}
};func maxSubarraySumCircular(nums []int) int {
total := 0
curMax, bestMax := 0, nums[0]
curMin, bestMin := 0, nums[0]
for _, x := range nums {
total += x
curMax = max(curMax+x, x)
bestMax = max(bestMax, curMax)
curMin = min(curMin+x, x)
bestMin = min(bestMin, curMin)
}
if bestMax < 0 {
return bestMax
}
return max(bestMax, total-bestMin)
}var maxSubarraySumCircular = function(nums) {
let total = 0;
let curMax = 0, bestMax = nums[0];
let curMin = 0, bestMin = nums[0];
for (const x of nums) {
total += x;
curMax = Math.max(curMax + x, x);
bestMax = Math.max(bestMax, curMax);
curMin = Math.min(curMin + x, x);
bestMin = Math.min(bestMin, curMin);
}
if (bestMax < 0) {
return bestMax;
}
return Math.max(bestMax, total - bestMin);
};function maxSubarraySumCircular(nums: number[]): number {
let total = 0;
let curMax = 0, bestMax = nums[0];
let curMin = 0, bestMin = nums[0];
for (const x of nums) {
total += x;
curMax = Math.max(curMax + x, x);
bestMax = Math.max(bestMax, curMax);
curMin = Math.min(curMin + x, x);
bestMin = Math.min(bestMin, curMin);
}
if (bestMax < 0) {
return bestMax;
}
return Math.max(bestMax, total - bestMin);
}其他解法
主解法用“总和减最小子数组和”的转化，O(1) 空间最省；前缀最大和枚举直接拼接后缀与前缀，思路更直观；单调队列解法最通用，能处理带长度限制的变形。
解法 2：前缀最大和枚举 时间 O(n)，空间 O(n)
跨越首尾的子数组由一段后缀和一段前缀拼成。先求 left[i]，表示以 nums[0] 开头、结尾不超过 i 的前缀的最大和，同时用 Kadane 求不跨越首尾的最大子数组和。再从右往左累加后缀和 suf，用 suf + left[i - 1] 更新答案。
直接枚举“后缀 + 前缀”的组合，不需要“总和减最小和”的转化，也不用单独处理全负数组。代价是多一个长度为 n 的数组。
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
n = len(nums)
left = [0] * n
left[0] = pre = nums[0]
cur = best = nums[0]
for i in range(1, n):
pre += nums[i]
left[i] = max(left[i - 1], pre)
cur = max(cur + nums[i], nums[i])
best = max(best, cur)
suf = 0
for i in range(n - 1, 0, -1):
suf += nums[i]
best = max(best, suf + left[i - 1])
return bestclass Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int pre = nums[0], cur = nums[0], best = nums[0];
left[0] = nums[0];
for (int i = 1; i < n; i++) {
pre += nums[i];
left[i] = Math.max(left[i - 1], pre);
cur = Math.max(cur + nums[i], nums[i]);
best = Math.max(best, cur);
}
int suf = 0;
for (int i = n - 1; i > 0; i--) {
suf += nums[i];
best = Math.max(best, suf + left[i - 1]);
}
return best;
}
}class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
int pre = nums[0], cur = nums[0], best = nums[0];
left[0] = nums[0];
for (int i = 1; i < n; i++) {
pre += nums[i];
left[i] = max(left[i - 1], pre);
cur = max(cur + nums[i], nums[i]);
best = max(best, cur);
}
int suf = 0;
for (int i = n - 1; i > 0; i--) {
suf += nums[i];
best = max(best, suf + left[i - 1]);
}
return best;
}
};func maxSubarraySumCircular(nums []int) int {
n := len(nums)
left := make([]int, n)
pre, cur, best := nums[0], nums[0], nums[0]
left[0] = nums[0]
for i := 1; i < n; i++ {
pre += nums[i]
left[i] = max(left[i-1], pre)
cur = max(cur+nums[i], nums[i])
best = max(best, cur)
}
suf := 0
for i := n - 1; i > 0; i-- {
suf += nums[i]
best = max(best, suf+left[i-1])
}
return best
}var maxSubarraySumCircular = function(nums) {
const n = nums.length;
const left = new Array(n).fill(0);
let pre = nums[0], cur = nums[0], best = nums[0];
left[0] = nums[0];
for (let i = 1; i < n; i++) {
pre += nums[i];
left[i] = Math.max(left[i - 1], pre);
cur = Math.max(cur + nums[i], nums[i]);
best = Math.max(best, cur);
}
let suf = 0;
for (let i = n - 1; i > 0; i--) {
suf += nums[i];
best = Math.max(best, suf + left[i - 1]);
}
return best;
};function maxSubarraySumCircular(nums: number[]): number {
const n = nums.length;
const left: number[] = new Array(n).fill(0);
let pre = nums[0], cur = nums[0], best = nums[0];
left[0] = nums[0];
for (let i = 1; i < n; i++) {
pre += nums[i];
left[i] = Math.max(left[i - 1], pre);
cur = Math.max(cur + nums[i], nums[i]);
best = Math.max(best, cur);
}
let suf = 0;
for (let i = n - 1; i > 0; i--) {
suf += nums[i];
best = Math.max(best, suf + left[i - 1]);
}
return best;
}解法 3：前缀和 + 单调队列 时间 O(n)，空间 O(n)
把数组复制一份接在后面，求长度 2n 的前缀和 pre。子数组 (i, j] 的和是 pre[j] - pre[i]，要求 j - n <= i < j。用单调递增的双端队列维护窗口内最小的 pre[i]，每个 j 用队首更新答案。
这是“长度不超过 n 的最大子数组和”的通用解法，可以推广到任意长度上限的问题。常数和空间都比主解法大。
from collections import deque
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
n = len(nums)
pre = [0] * (2 * n + 1)
for i in range(2 * n):
pre[i + 1] = pre[i] + nums[i % n]
dq = deque([0])
best = nums[0]
for j in range(1, 2 * n + 1):
while dq[0] < j - n:
dq.popleft()
best = max(best, pre[j] - pre[dq[0]])
while dq and pre[dq[-1]] >= pre[j]:
dq.pop()
dq.append(j)
return bestclass Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int[] pre = new int[2 * n + 1];
for (int i = 0; i < 2 * n; i++) pre[i + 1] = pre[i] + nums[i % n];
Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(0);
int best = nums[0];
for (int j = 1; j <= 2 * n; j++) {
while (dq.peekFirst() < j - n) dq.pollFirst();
best = Math.max(best, pre[j] - pre[dq.peekFirst()]);
while (!dq.isEmpty() && pre[dq.peekLast()] >= pre[j]) dq.pollLast();
dq.addLast(j);
}
return best;
}
}class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> pre(2 * n + 1, 0);
for (int i = 0; i < 2 * n; i++) pre[i + 1] = pre[i] + nums[i % n];
deque<int> dq;
dq.push_back(0);
int best = nums[0];
for (int j = 1; j <= 2 * n; j++) {
while (dq.front() < j - n) dq.pop_front();
best = max(best, pre[j] - pre[dq.front()]);
while (!dq.empty() && pre[dq.back()] >= pre[j]) dq.pop_back();
dq.push_back(j);
}
return best;
}
};func maxSubarraySumCircular(nums []int) int {
n := len(nums)
pre := make([]int, 2*n+1)
for i := 0; i < 2*n; i++ {
pre[i+1] = pre[i] + nums[i%n]
}
dq := []int{0}
best := nums[0]
for j := 1; j <= 2*n; j++ {
for dq[0] < j-n {
dq = dq[1:]
}
best = max(best, pre[j]-pre[dq[0]])
for len(dq) > 0 && pre[dq[len(dq)-1]] >= pre[j] {
dq = dq[:len(dq)-1]
}
dq = append(dq, j)
}
return best
}var maxSubarraySumCircular = function(nums) {
const n = nums.length;
const pre = new Array(2 * n + 1).fill(0);
for (let i = 0; i < 2 * n; i++) pre[i + 1] = pre[i] + nums[i % n];
const dq = [0];
let head = 0, best = nums[0];
for (let j = 1; j <= 2 * n; j++) {
while (dq[head] < j - n) head++;
best = Math.max(best, pre[j] - pre[dq[head]]);
while (dq.length > head && pre[dq[dq.length - 1]] >= pre[j]) dq.pop();
dq.push(j);
}
return best;
};function maxSubarraySumCircular(nums: number[]): number {
const n = nums.length;
const pre: number[] = new Array(2 * n + 1).fill(0);
for (let i = 0; i < 2 * n; i++) pre[i + 1] = pre[i] + nums[i % n];
const dq: number[] = [0];
let head = 0, best = nums[0];
for (let j = 1; j <= 2 * n; j++) {
while (dq[head] < j - n) head++;
best = Math.max(best, pre[j] - pre[dq[head]]);
while (dq.length > head && pre[dq[dq.length - 1]] >= pre[j]) dq.pop();
dq.push(j);
}
return best;
}