题目
很重要的一个转换是区间和能转变成前缀和相减.
那么那些前缀和很大 ,但又很靠前的位置肯定是不优的.
维护一个 坐标 和 值 都单调递增的队列.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N = 3e5+5; int n,m; int q[N] ; long long sum[N] , a[N]; long long ans = -1e12; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); sum[i] += sum[i-1] + a[i]; } int l = 1 , r = 1; q[1] = 0; for(int i=1;i<=n;++i) { while(l<=r && i-q[l] > m) ++l; ans = max(ans , sum[ i ] - sum[ q[l] ]); //cout<<q[l]<<' '<<q[r]<<endl; while(l<=r && sum[ q[r] ] >= sum[i]) --r; q[++r] = i; } printf("%lld",ans); return 0; }