解题思路
前缀和 + 单调队列 $O(n)$
代码
- 计算前缀和 f 然后针对第 i 个位置的前缀和 f(i)
- 去寻找他前面的位置 j 使得 f(j) 最小,(也就是 f(i) - f(j) 最大的位置)
- 同时这里的 i 和 j 之前的距离不可以超过 n
采用一个单调队列 来维护区间内的最小值
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> s(n * 2 + 1);
// 涉及到前缀和的问题,下标从 1 开始会更加方便
for (int i = 1; i <= n * 2; i++) {
s[i] = s[i - 1] + nums[(i - 1) % n]; // 每个 n 一循环
}
deque<int> que;
// 定义单调队列,是一个双端队列
que.push_front(0); // 区间是可以从下标 1 开始
int ans = INT_MIN;
for (int i = 1; i <= n * 2; i++) {
while (que.size() && i - que.front() > n) {
que.pop_front();
// 滑动窗口中的元素区间大于 n 从左侧删掉
}
ans = max(ans, s[i] - s[que.front()]);
while (que.size() && s[que.back()] >= s[i]) {
que.pop_back();
}
que.push_back(i);
}
return ans;
}
};
/*
从环中的任意一个位置断开,破环成链之后,都会找到一个在 2n 序列中一一对应的位置
等价于求 这个 2n 线段中,长度不超过 n 个最大连续子段和
预处理前缀和
*/