欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最大子序和:双向队列维护一个上升序列

程序员文章站 2024-03-18 21:50:46
...

最大子序和

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

注意: 子序列的长度至少是1。

输入格式
第一行输入两个整数n,m。
第二行输入n个数,代表长度为n的整数序列。
同一行数之间用空格隔开。

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

数据范围
1≤n,m≤300000
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7

题目不难,我们容易想到暴力枚举,其时间复杂度是O(n * m)的这显然是不可取的。
再后我们容易想到用前缀和来枚举暴力做法。
于是我们有了下面的推断。将距离小于等于m的一系列前缀和拿出。

我们容易想到,这里面的最大值一定是:最小的减去最大的,当然还要同时满足最小的在最大的前面。
我们再想一想。这假设上述的条件满足。
这两个数之间有一个数是有一个数是大于或者等于这个最大值的,那么这里就矛盾了。最大的差值一定不可能是这两个,因为前面已经找到更大的数对了,所以我们可以维护一个区间队列,这个区间队列是升序的。

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
ll s[N], n, m;
int q[N];
int main() {
    scanf("%lld %lld", &n, &m);
    ll temp;
    s[0] = 0;
    for(ll i = 1; i <= n; i++) {
        scanf("%lld", &temp);
        s[i] = s[i - 1] + temp;
    }
    int h = 0, t = 0;
    ll ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++) {
        if(i - q[h] > m)    h++;
        ans = max(ans, s[i] - s[q[h]]);
        while(h <= t && s[q[t]] >= s[i]) t--;//这里保证队列区间里的数是上升的。如果不是上升,从队尾删除元素。知道上升为止。
        q[++t] = i;
        // printf("%lld\n", ans);
    }
    printf("%lld", ans);
    return 0;
}
相关标签: 杂题