分析
-
双倍扩展数组
- 为了处理环形数组，将
nums 扩展为两倍长度的数组 s（模拟拼接后的连续数组），便于通过滑动窗口寻找环形最大子数组
-
前缀和数组
s[i] 表示从 nums[0] 到 nums[i % n] 的前缀和，通过前缀和计算任意区间的子数组和
-
滑动窗口 + 单调队列
- 维护一个单调递增的双端队列
q，存储前缀和的索引：
- 队首：保证窗口长度不超过
n，且队首元素是当前窗口内的最小前缀和
-
动态更新结果
- 在每一步中计算
s[i] - s[q.front()]，更新最大子数组和
时间复杂度
总时间复杂度 O(n)，每个元素最多进出队列一次，遍历一遍即可得到结果
空间复杂度
空间复杂度为 O(n)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution
{
public:
int maxSubarraySumCircular(vector<int>& nums)
{
int n = nums.size();
std::vector<int> s(n * 2); // 扩展两倍长度的前缀和数组
s[0] = nums[0];
// 构建前缀和数组
for (int i = 1; i < n * 2; ++i)
s[i] = s[i - 1] + nums[i % n];
std::deque<int> q; // 单调队列存储前缀和的索引
q.push_front(0);
int res = INT_MIN;
for (int i = 1; i < n * 2; ++i)
{
// 窗口长度大于 n 时弹出队首
while (q.size() && i - q.front() > n)
q.pop_front();
// 更新最大子数组和
res = std::max(res, s[i] - s[q.front()]);
// 维护单调递增的队列
while (q.size() && s[i] <= s[q.back()])
q.pop_back();
q.push_back(i);
}
return res;
}
};
|
