AcWing:135. 最大子序和(前缀和 + 单调队列)
2024-09-05 09:06:54
输入一个长度为n的整数序列,从中找出一段长度不超过m的连续子序列,使得子序列中所有数的和最大。
输入格式
第一行输入两个整数n,m。
第二行输入n个数,代表长度为n的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
1≤n,m≤3000001≤n,m≤300000
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
算法:前缀和 + 单调队列
注意:单调队列需要使用双端队列deque,因为其中需要头部弹出以及尾部弹出。
#include <iostream>
#include <cstdio>
#include <deque> using namespace std; #define INF 0x3f3f3f3f const int maxn = 3e5+; deque<int> que; int arr[maxn];
int sum[maxn]; int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &arr[i]);
sum[i] = sum[i - ] + arr[i];
}
int ans = -INF;
for(int i = ; i <= n; i++) {
while(!que.empty() && i - que.front() > m) { //如果队列里面的数超过了m的话,就将前面的弹出
que.pop_front();
}
int k;
if(que.size() > ) {
k = que.front();
} else {
k = ;
}
ans = max(ans, sum[i] - sum[k]);
while(!que.empty() && sum[que.back()] >= sum[i]) { //利用前缀和来维护单调队列,根据前缀和的性质,
que.pop_back();
}
que.push_back(i);
}
cout << ans << endl;
return ;
}
最新文章
- JavaScript 嵌套 书名号 查询
- com.sun.org.apache.xerces.internal.impl.io.MalformedByteSequenceException: 3 字节的 UTF-8 序列的字节 3 无效。
- VS2010常用快捷键
- ios7.1 在线安装 失败的解决办法
- Java中实例方法,实例变量,静态方法,静态变量,final方法重写的问题,覆盖
- PowerShell为什么强大
- 基于CBOW网络手动实现面向中文语料的word2vec
- Golang的优雅重启
- cookie、sesstion、strorage
- java使用freemarker模板导出word(带有合并单元格)文档
- 函数调用的四种方式 和 相关的 --- this指向
- Android 获取联系人和电话号码
- jQuery stop()的用法
- Spring如何解析Dubbo标签
- JSP 页面重定向
- android unity3d开发学习第一步
- windows 键盘全局钩子
- Lambda01 编程范式、lambda表达式与匿名内部类、函数式接口、lambda表达式的写法
- PHPExcel读写封装
- 【ORACLE】ORA-27102: out of memory报错的处理