最大连续和

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 873 字

从长度为n的序列中取一段长度不超过m的非空连

一本通
例

正文

/*
原题：T1598 「一本通 5.5 例 2」最大连续和
题意：从长度为 n 的序列中取一段长度不超过 m 的非空连续子段，使其和最大。
思路：前缀和 s[i]，答案 = max_{i}(s[i] - min_{j∈[i-m,i-1]} s[j])；
     用递增单调队列在窗口内维护最小的 s[j]，O(1) 取得最小值。
复杂度：时间 O(n)，空间 O(n)。
易错点：子段非空且长度 ≤m；j 可取 0（空前缀）表示子段从 1 开始；用 long long 防溢出。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<long long> s(n+1,0);
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        s[i]=s[i-1]+x;
    }
    deque<int> q;
    q.push_back(0);
    long long ans=LLONG_MIN;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front()<i-m){
            q.pop_front();
        }
        ans=max(ans,s[i]-s[q.front()]);
        while(!q.empty()&&s[q.back()]>=s[i]){
            q.pop_back();
        }
        q.push_back(i);
    }
    cout<<ans<<'\n';
    return 0;
}

最大连续和

正文

一本通·提高篇的其它内容