热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【集训Day3单调队列】【2018寒假集训Day5更新】最大子序列和

最大子序列和(maxsum)【问题描述】输入一个长度为n的整数序列(A1,A2,……,An),从中找出一段连续的长度不超过M的子序列,使得这个序列的和最大。例如:序列1,-3,5

最大子序列和(maxsum)
【问题描述】
输入一个长度为n的整数序列(A1,A2,……,An),从中找出一段连续的长度不超过M的子序列,使得这个序列的和最大。
例如:
序列 1, -3, 5, 1, -2, 3
当M=2或3时,S=5+1=6;当M=4时,S=5+1+(-2)+3=7。
【输入格式】
输入文件第一行一个整数n表示序列的长度,第二行n个整数,代表序列的元素。第三行一个整数表示M。
【输出格式】
一个整数,即子序列的最大和。保证结果不超过longint范围。
【输入样例】
6
1 -3 5 1 -2 3
3
【输出样例】
6
【数据范围】
50%的数据N,M<=1000
100%的数据N,M<=20000
【解题思路】
求出前缀和后,a[i]+a[i+1]……+a[j]就可以用sum(前缀和数组)[j]-sum[i]+a[i]得出,那么我们只需要让j-i+1<=m同时让sum[j]最大,而j的范围可以是i+1、i+2…i+m-1,那么就变成了一个求出固定区间长度为m的最大值。

更正:求出前缀和后,a[i-m+1]+a[i-m+2]……+a[i]就可以用sum(前缀和数组)[i]-sum[i-m]得出,那么我们只需要在这个区间里寻找最小的sum[j],j的范围是i-m+1<=j<=i,那么就变成了一个求出长度为m的固定区间的最大值。
【解题反思】

  • 队列中不必要存入数据,可以存入下标。
  • 在判断队头是否在区间内时,求出队列长度不是用尾指针的值减去头指针。用队列中尾指针指向的位置减去头指针指向的位置加上1的值才是队列长度。

【参考程序】

#include
#include
using namespace std;
int n,m,a[200001];
int sum[200001],b[200001],maxans;
int main()
{
freopen("maxsum.in","r",stdin);
freopen("maxsum.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
scanf("%d",&m);
int head=1,tail=1,i=1;
while (i<=n)
{
while (sum[i]<=sum[b[tail]]&&tail>=head)
tail--;
tail++;
b[tail]=i;
if (b[tail]-b[head]+1>m&&head maxans=max(maxans,sum[i]-sum[b[head]]);
i++;
}
cout< return 0;
}

推荐阅读
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 本文详细介绍了Linux系统中信号量的相关函数,包括sem_init、sem_wait、sem_post和sem_destroy,解释了它们的功能和使用方法,并提供了示例代码。 ... [详细]
  • 在尝试加载支持推送通知的iOS应用程序的Ad Hoc构建时,遇到了‘no valid aps-environment entitlement found for application’的错误提示。本文将探讨此错误的原因及多种可能的解决方案。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 本文介绍如何手动实现一个字符串连接函数,该函数不依赖于C语言的标准字符串处理函数,如strcpy或strcat。函数原型为void concatenate(char *dest, char *src),其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]
  • 本文详细介绍了如何在循环双链表的指定位置插入新元素的方法,包括必要的步骤和代码示例。 ... [详细]
  • 函子(Functor)是函数式编程中的一个重要概念,它不仅是一个特殊的容器,还提供了一种优雅的方式来处理值和函数。本文将详细介绍函子的基本概念及其在函数式编程中的应用,包括如何通过函子控制副作用、处理异常以及进行异步操作。 ... [详细]
  • 本文将深入探讨C语言中的位操作符——按位与(&)、按位或(|)和按位异或(^),通过具体示例解释这些操作符如何在位级别上对数据进行操作。 ... [详细]
  • 本文详细介绍了JQuery Mobile框架中特有的事件和方法,帮助开发者更好地理解和应用这些特性,提升移动Web开发的效率。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • 本文通过分析一个具体的案例,探讨了64位Linux系统对32位应用程序的兼容性问题。案例涉及OpenVPN客户端在64位系统上的异常行为,通过逐步排查和代码测试,最终定位到了与TUN/TAP设备相关的系统调用兼容性问题。 ... [详细]
  • protobuf 使用心得:解析与编码陷阱
    本文记录了一次在广告系统中使用protobuf进行数据交换时遇到的问题及其解决过程。通过这次经历,我们将探讨protobuf的特性和编码机制,帮助开发者避免类似的陷阱。 ... [详细]
author-avatar
欢乐乡村烤鸭8321
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有