[CH1201]最大子序和

单调队列模板题。

#include <bits/stdc++.h>
#define MAXN 300000
#define ll long long
using namespace std;

ll n,m,ans;
ll sum[MAXN];
deque<int> q;

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    ll temp;
    for(int i = 1; i <= n; ++i) {
        cin >> temp;

        sum[i] = sum[i-1] + temp; 
    }

    for(int i = 1; i <= n; ++i) {
        //维护题目性质(小于等于m个)
        while(!q.empty() && q.front() + m > i)
            q.pop_front();

        //维护答案
        ans = max(ans,sum[i] - sum[q.front()]);

        //维护单调队列性质
        while(!q.empty() && sum[q.back()] >= sum[i])
            q.pop_back();

        q.push_back(i);
    }

    cout << ans << endl;

    return 0;
}
Last modification:April 13th, 2019 at 04:43 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment