题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <limits.h>
using namespace std;

int main(){
    int n , m ;
    int res = INT_MIN;
    cin >> n >> m;
    deque<int> q; //记录的是下标
    q.push_back(0);

    vector<int> nums(n + 1);

    for(int i = 1 ; i <= n ; i++){
        cin >> nums[i];
        nums[i] += nums[i - 1]; // 计算前缀和
    }

    for(int i = 1; i <= n ; i++){
        if(i - q.front() > m ) // 确保使前m项和
            q.pop_front();

        //维护一个单调递增的队列
        while(!q.empty() && nums[q.back()] >= nums[i]) q.pop_back();

        //nums[i] - nums[q.front()]表示前m缀和
        res = max(res , nums[i] - nums[q.front()]); 

        q.push_back(i);
    }

    cout << res << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <limits.h>
using namespace std;

const int N = 10000;
int q[N]; //记录的是下标

int main(){
    int n , m ;
    int res = INT_MIN;
    cin >> n >> m;
    vector<int> nums(n + 1);

    for(int i = 1 ; i <= n ; i++){
        cin >> nums[i];
        nums[i] += nums[i - 1]; // 计算前缀和
    }

    int hh = 0 , tt  = 0; // 队头和队尾
    for(int i = 1 ; i <= n ; i++){

        if(i - q[hh] > m) hh++;

        //nums[i] - nums[q[hh]] 表示前m缀和
        res = max(res , nums[i] - nums[q[hh]]);
        //cout << res << " ";
        //维护一个队头到队尾使单调递增的队列 使队头元素最小
        while(hh <= tt && nums[q[tt]] >= nums[i]) tt--;
        q[++tt] = i;

    }
    //cout << endl;
    cout << res << endl;
    return 0;

}