洛谷 T478345：循环数组 ← 单调队列 + 破环成链
【题目来源】
https://www.luogu.com.cn/problem/T478345
【题目描述】
给你一个循环的数组 A[1], A[2], A[3], ...., A[n]。循环的数组意思是 A[1] 的左边是 A[n]，A[n] 的右边是 A[1]，也就是可以理解为他们连成了一个环。
现在你的任务是找到一个字串（ A[1,2,3] 算子串，A[n-1,n,1,2] 也算，但是必须连续，A[1,3,4] 则不算），这个子串要求长度小于等于 K。在这个要求下，子串的元素和最大能是多少?
注意子串不能为空。1<=N<=1000000，1<=K<=N，-1000<=A[i]<=1000
【输入格式】
第一行两个整数，N，K，空格隔开。
接下来一行 N 个数，空格隔开，为数组元素 A[1] ... A[n]。
【输出格式】
输出一行，为一个整数，代表最大和。
【输入样例】
6 3
6 -1 2 -6 5 -5
【输出样例】
7
【数据范围】
1<=N<=1000000，1<=K<=N，-1000<=A[i]<=1000
【算法分析】
● 环形数组的经典处理技巧：破环成链，将原数组拼接一份，得到长度为 2N 的数组，原环形的任意连续子串都对应新数组的一段长度 ≤K 的连续子串。
● 前缀和 + 单调队列优化：利用前缀和将「区间和」转化为「两个前缀和的差值」，用单调队列维护前缀和的最小值，从而在 O(N) 时间内找到最优解。
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=1e6+5; LL imax=LLONG_MIN; LL s[maxn<<1]; //presum int a[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; for(int i=1; i<=n; i++) { cin>>a[i]; } for(int i=1; i<=n+k; i++) { //破环成链 s[i]=s[i-1]+a[(i-1)%n+1]; //环形取数 } deque<int> q; //单调队列存下标，保证s[下标]单调递增 q.push_back(0); for(int i=1; i<=n+k-1; i++) { while(!q.empty() && q.front()<i-k) { q.pop_front(); } if(!q.empty()) { imax=max(imax,s[i]-s[q.front()]); } while(!q.empty() && s[i]<=s[q.back()]) { q.pop_back(); } q.push_back(i); } cout<<imax<<endl; return 0; } /* in: 6 3 6 -1 2 -6 5 -5 out: 7 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143176072
https://www.luogu.com.cn/problem/T478345