AcWing 135. 最大子序和

题目描述

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。

输入格式
第一行输入两个整数n,m。

第二行输入n个数，代表长度为n的整数序列。

同一行数之间用空格隔开。

输出格式
输出一个整数，代表该序列的最大子序和。

数据范围
1≤n,m≤300000

样例

1
2
3
4
5
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

思路：

求一个区间长度为M的序列和可以用前缀和相减的形式来得到：

1
k = sum[i]- sum[i-M]

而要求当前区间P内的最大值，可以找到该区间（sum[i-1]–sum[i-m]）内的最小值，用sum[i]减去该值，得到以sum[i]为终点的区间的最大值，对于每个区间，都求得一个最大值，再到这些之内取最大即为答案。

所以现在的问题变为：给定一个区间，如何找出给区间内的最小值。

如果暴力求，会使总的复杂度为O(N2)，不符合要求。
再看一下要解决的问题，我们想到使用单调队列，可以在线求出一组序列的最值，所以我们使用一个大小为M的队列来维护最值。

这样总的复杂度就为线性的了。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<deque>
#include<cstdio>
using namespace std;
const int MAXN = 1e6+10;
long long a[MAXN],sum[MAXN],ans = -1e10;

int main(){
    deque<int> q;
    int N,M;
    cin >> N >> M;
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 1; i <= N; i++) sum[i] = sum[i-1] + a[i-1]; //前缀和
    for(int i = 1; i <= N; i++){
        while(q.size() && q.front() < i - M) q.pop_front(); //超出窗口范围，清除
        ans = max(ans, sum[i]-sum[q.front()]); //更新值
        while(q.size() && sum[q.back()] > sum[i]) q.pop_back(); //维护单调性质
        q.push_back(i);
    }
    cout << ans;
    return 0;
}