最大子序和(单调队列)

发表于 | 更新于 | 分类于

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

输入格式

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

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

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

输出格式

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

数据范围

1≤n,m≤300000

输入样例：

1
2
6 4
1 -3 5 1 -2 3

输出样例：

7

思想:

tips: 求m连续区间内大于某数可以用尺取法。
1.这道题利用前缀和将区间加和转化为两点相减问题就转化为了在m之内，
求最大纵坐标差。
2.利用队列来维护单调性 - 单调队列

  • 先预处理出前缀和，队列里首先入0来处理出边界sum[r] - sum[l - 1],当一个元素入队时，
    如果sum[i] - q[l] > m，一直出队队首直到相距距离 <= m
  • 更新答案，由于是单调的，则sum[i] - sum[q[l]]是当前最小。
  • 若sum[i] >= sum[q[r]]，则将队尾出队，由于q[0] = 0, 最后会在此停下
  • 新元素入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;		//和爆int
const int N = 3e5 + 5;
ll s[N];		//前缀和数组
int q[N];		//数组模拟队列
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )	//前缀和下标一般从1开始
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];		//预处理前缀和
    }
    int l = 0, r = 0;	//队首，队尾
    ll ans = 0;
    for(int i = 1; i <= n; i ++ )
    {
        while(l <= r && i - q[l] > m)   l ++;		//挪动队首直到不 > m
        ans = max(ans, s[i] - s[q[l]]);		//更新答案
        while(l <= r && s[i] <= s[q[r]]) r --;		//队尾出队维护单调性
        q[++ r] = i;		//新元素入队
    }
    cout << ans << endl;
    return 0;
}
0%