题目描述
输入一个长度为n的整数序列,从中找出一段长度不超过m的连续子序列,使得子序列中所有数的和最大。
输入格式
第一行输入两个整数n,m。
第二行输入n个数,代表长度为n的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
1≤n,m≤300000
样例
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
单调队列 O(N)
重新写一遍。。。
计算区间和,我们很容易想到前缀和,也就是说我们要查询[l,r]区间的值,我们显然会这样处理。
sum[r]−sum[l−1]sum[i]表示[1,i]的和
这句话就是我们非常熟悉的前缀和求区间和。
那么这道题目如何处理呢?
我们发现我们的目标就是
找到两个位置l,r,要求
- r−l≤M 也就是说区间的大小不可以超过M
- sum[r]−sum[l] 尽量大.
这么说来,我们完全可以O(n2)枚举l,r不就好了吗?
但是时间复杂度说:臣妾做不到
所以说,我们只能够通过单调队列来处理这道题目了。
单调队列是什么,欢迎阅读博主的文章
我们着重理解一下如何单调队列。
我们发现假如说我们的右端点r,固定好了,那么我们的问题就变化了。
找到一个左端点l,要求j∈[i−m,i−1].
这句话的意思就是说,我们这个区间长度不可以超过m,而且区间长度至少为1. 这不是废话嘛
而且呢sum[j]要尽量的小,为了使得区间和最大,对吧。
所以说咱们发现,这个j的取值,是一个区间,而且最主要的是,我们只要这个区间的最值。
区间最值,就可以通过单调队列处理。
我们发现如果说有一个位置k,这个k<j<i.而且sum[k]≥sum[j]
用人话说就是,一个人比你先学习,也就是比你老,而且实力还不如你,那么请问这个人打得赢你吗?
对不起,实力不允许,蒟蒻我打赢大佬你。
我们来理性分析一遍。
k<j,也就是说[k,i]这个区间的长度,一定是大于[j,i]这个区间长度的。
sum[k]≥sum[j],这么说来的话,那么sum[i]−sum[k]≥sum[i]−sum[j],也就是说我们的[k,j]区间消耗更大。
既然如此,那么k是真的很菜,是真的没有用了。
我们的j,不仅比k更加接近i,最主要的是,消耗比k小。
那么我们还有什么理由选择k呢。
一个机器,我们当然是选择,又新,消耗又少的,肯定不会选择又老,还消耗大的。
绿色蓝天,从我做起。—公益广告
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=300100;
deque<long long> q;
long long n,m,l,r,s[N],a[N],ans;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
fir(i,1,n)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
fir(i,1,n)
{
while(q.size() && q.front()<i-m)//如果队头已经无法满足区间长度小于m的话,那么弹出
q.pop_front();//队头不满足,不需要,弹出.
ans=max(ans,s[i]-s[q.front()]);//取当前最优值
while(q.size() && s[q.back()]>=s[i])//如果说队尾大于当前值的话.
q.pop_back();//不需要,弹出
q.push_back(i);//将i放入队尾.
}
cout<<ans;
return 0;
}
Orz
讲得真好
%%%%%%%%%%%%%%%5
秦大佬,这代码ac不了。 建议在看一下 不过秦大佬的题解思路是说得真的好
加个ans = -1e7 试试
的确得加
这代码ac不了啊
给个初始化q.push_back(0);就可以了
大佬 这个地方sum[i]−sum[k]≥sum[i]−sum[j]是不是写反了 应该是小于等于把
对
5 3
1 2 3 -2 -2 为什么输出5 不应该是 6嘛
q.push_back(0)就好了 作者可能忘记了hh
我发现我是那个k o(╥﹏╥)o
大佬, 队列里维护的是m个数吗,q.front()<i-m;是为什么啊?单调队列的出队总是写不对
当前是i,但是队头到当前位置,已经大于m,那么肯定就已经无效了,不管怎么说,队头到当前位置,已经大于m了。
这是您的解释……我有不明白的,已经加粗了。
和楼下dalao同问,毕竟lyd老师书上的确说是s[k]≥s[j],这里要求的是最大子段和呀。
如果我有理解错的地方,还望指出。
我已经怀疑我自己脑袋了,马上修改了!!!
qwq
报告大佬,修改完毕了!
不应该是s[k] >= s[j]吗
为什么要是sk>=sj呢?这里当然要是sk<sj,因为k在j的前面,而且还小的话,我们才会踢掉k的.如果大于的话,我们就不能保证sk一定没有用了.
因为s[j]点值又小,答案s[i]−s[j]肯定比s[i]−s[j]越大
这不就是说s[k] >= s[j]吗
您又带错了吧.
我们要保留j,抛去k.
那么必须满足.
1. j在后面
2. s[k]≤s[j]
我是写错了 但是我还不明白
就是确定了右端点,那左端点就应该越小越好吧
如果 k <= j && s[k] >= s[j] 才是k没有j优吧
哪里错了的话望耐心指正
稍等啊,我先吃个晚饭.
我可能有点不清楚了,我明天上午给您再写一次题解吧.
我可能题解没写好,导致您理解上有问题了.
@颂安
多谢qwq
修改完毕了@颂安
为什么博主的代码我编译运行会出现队列没有元素但是调用了front()的错误导致程序崩溃,但是提交却是对的?
因为C++编译器版本不同,再加上数据特殊性.当然了,最好还是代码修改修改,添加一个空数,就像楼下@[寻人启事_()].大佬所言
双端队列里一开始不插一个0进去没问题吗?
我们这里有一个size函数判断队列里面是否有数,自然而然,就不会出现溢出等问题了.
在第一步的时候 队列是没有值的,可是用一个front() ?
其实没有问题的
可以过, 但感觉有点不对。
虽然说队列里面没有任何值,但是返回的值是不会影响答案的.其实你可以自己看看C++中STL库,或者晚上找找STLblog就好了,这一点其实我自己也不是特别清楚,所以我建议您最好还是利用搜索引擎
虽然说队列里面没有任何值,但是返回的值是不会影响答案的.其实你可以自己看看C++中STL库,或者晚上找找STLblog就好了,这一点其实我自己也不是特别清楚,所以我建议您最好还是利用搜索引擎
输出了一下,发现队列为空的时候front()返回0
其实好像不一定这样吧