AcWing 135. 最大子序和(使用deque的正确题解)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 135. 最大子序和(使用deque的正确题解) 原题链接简单

作者：

负壹 , 2020-06-22 13:51:32 , 所有人可见 , 阅读 2078

7

3

C++ 代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int N = 300010;
int n,m;
int s[N];

int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>s[i];
        s[i] += s[i-1];
    }

    int res = s[1];
    deque<int>q;
    q.push_back(0);
    for(int i = 1;i<=n;i++){
        while(q.size()&&q.front()<i-m)q.pop_front();
        if(q.size())res = max(res,s[i]-s[q.front()]);
        else res = max(res,s[i]-s[i-m]);
        while(q.size()&&s[i]<=s[q.back()])q.pop_back();
        q.push_back(i);
    }
    cout<<res;
    return 0;
}

9 评论

zmy 2020-08-03 22:55

s[i-m]不会溢出吗？

烟花易冷 2020-08-05 21:57

我注释了这行也ac了

zmy 2020-08-05 22:15 回复了烟花易冷的评论

我明白了，一开始的时候把0加入队列中，所以队列中一直不空，所以那句代码就是没用的了

烟花易冷 2020-08-05 22:18 回复了烟花易冷的评论

#include <bits/stdc++.h>
using namespace std;
const int N = 300010; 
long long s[N]; // 前缀和数组
deque<int> q;// 单调队列 
int n, m;
long long res = INT_MIN;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> s[i];
        s[i] += s[i - 1];// 计算前缀和数组 
    }
    q.push_back(0);
    for(int i = 1; i <= n; i ++)// 递增队列
    {
        if(q.front() < i - m)// 如果当前元素的下标与队头元素下标的距离超过m
            q.pop_front();// 队头出队   
        if(!q.empty() )
            res = max(res, s[i] - s[q.front()]);// 当前元素与队头元素之差即集合元素之和
        while(!q.empty() && s[i] <= s[q.back()])// 当前元素小于队尾元素 
            q.pop_back();// 队尾出队 
        q.push_back(i);
    }
    cout << res; 
    return 0;
}