环上最大连续和

给定N,K以及一个环：A[1],A[2],A[3],…A[N]，其中A[1]的左边是A[N]。
求该环上最大的连续子段和，要求选出的子段长度不超过K。

输入描述:

第一行两个整数N和K。
接下来一行，N个整数表示A[i]。

输出描述:

输出题目要求的最大连续和。

示例1
输入

6 3
6 -1 2 -6 5 -5

输出

7

示例2
输入

6 4
6 -1 2 -6 5 -5

输出

7

示例3
输入

6 3
-1 2 -6 5 -5 6

输出

7

示例4
输入

6 6
-1 -1 -1 -1 -1 -1

输出

-1

说明

1<=K<=N<=10^5, -10^3<A[i]<10^3

huanshangzuidalianxu.cppview raw

/*
 环的问题一般把序列变成两倍
 预处理出前缀和
 枚举右端点i，sum[i]-sum[x]最大，x需要在某个范围内sum[x]最小，使用单调队列
 */
#include<bits/stdc++.h>
#define M 200005
using namespace std;
int q[M],sum[M];
int main() {
    int n,k,l=1,r=1,ans=-2e9,al,ar;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++) {
        scanf("%d",&sum[i]);
        sum[i]+=sum[i-1];
    }
    for(int i=n+1; i<n+k; i++)sum[i]=sum[n]+sum[i-n];
    q[r]=0;
    for(int i=1; i<n+k; i++) {
        while(r>=l&&i-q[l]>k)l++;
        if(r>=l&&ans<sum[i]-sum[q[l]]) {
            ans=sum[i]-sum[q[l]];
        }
        while(r>=l&&sum[q[r]]>=sum[i])r--;
        q[++r]=i;
    }
    printf("%d\n",ans);
    return 0;
}