ContestHunter 1201 最大子序和
2024-10-08 08:28:53
描述
输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。
例如 1,-3,5,1,-2,3
当m=4时,S=5+1-2+3=7
当m=2或m=3时,S=5+1=6
输入格式
第一行两个数n,m(n,m<=300000)
第二行有n个数,要求在n个数找到最大子序和
输出格式
一个数,数出他们的最大子序和
样例输入
6 4
1 -3 5 1 -2 3
样例输出
7
这题是单调队列的典型题。首先可以把区间和问题转换为两个前缀和相减的问题。朴素算法就是枚举左右端点,但算法复杂度为O(n^2),这道题显然是过不了的。
所以我们可以只枚举右端点i,当i固定时,找一个左端点j,其中j属于[i-m,i-1]并且sum[j]最小。
不妨比较一下任意两个位置j和k,如果k<j<i并且是sum[k]>=sum[j],那么对所以大于等于i的右端点来说,k都不会是一个好选择,直接移除队列比较好。
代码如下
#include<bits/stdc++.h>
using namespace std;
int a[],q[],sum[];
int main()
{
int n,m;
cin>>n>>m;
for(int i=;i<=n;i++)
cin>>a[i];
for(int i=;i<=n;i++)
{
sum[i]=sum[i-]+a[i];
}
int l=,r=,ans=-;
q[]=;
for(int i=;i<=n;i++)
{
while(l<=r&&q[l]<i-m)
l++;
ans=max(ans,sum[i]-sum[q[l]]);
while(l<=r&&sum[q[r]]>=sum[i])
r--;
q[++r]=i;
}
cout<<ans<<endl; return ;
}
最新文章
- Linux环境部署(JDK/Tomcat/MySQL/证书)
- PostgreSQL 在centos 7下的安装配置
- MySQL执行计划解读
- ubuntu安装配置jdk tomcat mysql ...
- 使用预处理PreparedStatement执行Sql语句
- MSSQL大全
- 关于hadoop2.4.1伪分布式系统的搭建
- 2015第37周五javascript函数arguments对象巧用一
- JS数组删除一个元素(根据值删)
- 开发移动端web应用, 使用手机自带键盘的搜索按钮
- C++学习笔记6
- Fast portable non-blocking network programming with Libevent
- JavaScript 作用域 匿名函数 模仿块级作用域(私有作用域)
- js添加div
- 2018-2019-2 20165232《网络对抗技术》Exp1 缓冲区溢出实验
- 素数定理π(n)~n/lnn弱化版证明
- Thrift IDL
- MyBatis 3 使用注解配置SQL映射器
- gitlab 部署
- 2017-2018-2 20155204《网络对抗技术》EXP5 MSF基础应用