最长递增——蓝桥杯
1.题目描述
在数列 a1,a2,⋯,an 中,如果ai<ai+1<ai+2<⋯<aj,则称 ai 至 aj 为一段递增序列,长度为 j−i+1。
定一个数列,请问数列中最长的递增序列有多长。
输入描述
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋯,an,相邻的整数间用空格分隔,表示给定的数列。
其中, 2≤n≤1000,0≤数列中的数≤104。
输出描述:
输出一行包含一个整数,表示答案。
输入输出样例
示例
输入
7
5 2 4 1 3 7 2
输出
3
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
2.代码
#include <iostream> // 引入输入输出流库
using namespace std; // 使用标准命名空间int main() // 主函数
{int n; // 定义一个整数n,用于存储数列的长度cin >> n; // 从标准输入读取n的值int a[n+2]; // 定义一个大小为n+2的整数数组a,用于存放数列(多开两个空间以防止越界)int len = 1, maxn = 1; // 定义两个整数len和maxn,分别用于记录当前递增序列的长度和最长递增序列的长度,初始值都设为1for (int i = 0; i < n; i++) // 循环读取n个整数并存入数组a中{cin >> a[i];}for (int i = 1; i < n; i++) // 从数组的第二个元素开始遍历{if (a[i] > a[i - 1]) // 如果当前元素大于前一个元素,说明递增序列还在继续{len++; // 递增序列长度加1if (i == n - 1 && maxn < len) // 如果当前元素是数组的最后一个元素,并且当前递增序列长度大于已知的最长递增序列长度{maxn = len; // 更新最长递增序列长度}}else // 如果当前元素不大于前一个元素,说明递增序列结束{if (maxn < len) // 如果当前递增序列长度大于已知的最长递增序列长度{maxn = len; // 更新最长递增序列长度}len = 1; // 重置当前递增序列长度为1}}cout << maxn << endl; // 输出最长递增序列的长度return 0; // 返回0,表示程序正常结束
}
3.解题想法
以上代码的思路主要是通过一次遍历来找出数列中的最长递增子序列的长度。具体来说,它使用了一个变量len来记录当前递增序列的长度,另一个变量maxn来记录最长递增序列的长度。遍历数列时,如果当前元素大于前一个元素,则len加1;否则,将len与maxn比较并更新maxn,然后将len重置为1。
优点:
1. 简单直观:代码逻辑清晰,容易理解和实现。
2. 时间复杂度低:只需遍历一次数列,时间复杂度为O(n),效率较高。
3. 空间复杂度低:只使用了常数级别的额外空间,空间复杂度为O(1)。
缺点:
1. 边界条件处理复杂:需要特别处理最后一个元素的递增序列情况,增加了代码的复杂性。
2. 不够灵活:如果需要处理更复杂的序列问题(如最长非递减子序列),需要对代码进行较大修改。
枚举法的改进:
如果你希望在找到一个递增序列后,能够从下一个元素开始继续查找,而不是从头开始,可以使用动态规划的方法来改进。具体来说,可以使用一个数组dp来记录以每个元素结尾的最长递增子序列的长度。
相关文章:
最长递增——蓝桥杯
1.题目描述 在数列 a1,a2,⋯,an 中,如果ai<ai1<ai2<⋯<aj,则称 ai 至 aj 为一段递增序列,长度为 j−i1。 定一个数列,请问数列中最长的递增序列有多长。 输入描述 输入的第一行包含一个整数 n。…...
【MFC】C++所有控件随窗口大小全自动等比例缩放源码(控件内字体、列宽等未调整) 20250124
MFC界面全自动等比例缩放 1.在初始化里 枚举每个控件记录所有控件rect 2.在OnSize里,根据当前窗口和之前保存的窗口的宽高求比例x、y 3.枚举每个控件,根据比例x、y调整控件上下左右,并移动到新rect struct ControlInfo {CWnd* pControl;CRect original…...
C#标准Mes接口框架(持续更新)
前言 由于近期我做了好几个客户的接入工厂Mes系统的需求。但是每个客户的Mes都有不同程度的定制需求,原有的代码复用难度其实很大。所以打算将整个接入Mes系统的框架单独拿出来作为一个项目使用,同时因为不同的设备接入同一个Mes系统,所以代…...
【Uniapp-Vue3】动态设置页面导航条的样式
1. 动态修改导航条标题 uni.setNavigationBarTitle({ title:"标题名称" }) 点击修改以后顶部导航栏的标题会从“主页”变为“动态标题” 2. 动态修改导航条颜色 uni.setNavigationBarColor({ backgroundColor:"颜色" }) 3. 动态添加导航加载动画 // 添加加…...
SQL 递归 ---- WITH RECURSIVE 的用法
SQL 递归 ---- WITH RECURSIVE 的用法 开发中遇到了一个需求,传递一个父类id,获取父类的信息,同时获取其所有子类的信息。 首先想到的是通过程序中去递归查,但这种方法着实孬了一点,于是想,sql能不能递归查…...
期权帮|如何利用股指期货进行对冲套利?
锦鲤三三每日分享期权知识,帮助期权新手及时有效地掌握即市趋势与新资讯! 如何利用股指期货进行对冲套利? 对冲就是通过股指期货来平衡投资组合的风险。它分为正向与反向两种策略: (1)正向对冲ÿ…...
INCOSE需求编写指南-第1部分:介绍
第1部分:介绍Section 1: Introduction 1.1 目的和范围 Purpose and Scope 本指南专门介绍如何在系统工程背景下以文本形式表达需求和要求陈述。其目的是将现有标准(如 ISO/IEC/IEEE 29148)中的建议以及作者、主要贡献者和审稿员的最佳实践结…...
FFPlay命令全集合
FFPlay是以FFmpeg框架为基础,外加渲染音视频的库libSDL构建的媒体文件播放器。 ffplay工具下载并播放视频,可以辅助卡看流信息。 官网下载地址:http://ffmpeg.org/download.html#build-windows 下载build好的exe程序: 此处下载…...
Mono里运行C#脚本34—内部函数调用的过程
本文来分析Mono运行脚本时,会调用一些C实现的函数代码。 而这个过程又是怎么样实现的呢? 比如前面分析的脚本: IL_0000: call string class MonoEmbed::gimme() 在这里会调用C函数实现的MonoEmbed::gimme()函数。 而这个函数是在C程序内部实现,通过下面的代码来注册到运行…...
rust feature h和 workspace相关知识 (十一)
feature 相关作用和描述 在 Rust 中,features(特性) 是一种控制可选功能和依赖的机制。它允许你在编译时根据不同的需求启用或禁用某些功能,优化构建,甚至改变代码的行为。Rust 的特性使得你可以轻松地为库提供不同的…...
-bash: ./uninstall.command: /bin/sh^M: 坏的解释器: 没有那个文件或目录
终端报错: -bash: ./uninstall.command: /bin/sh^M: 坏的解释器: 没有那个文件或目录原因:由于文件行尾符不匹配导致的。当脚本文件在Windows环境中创建或编辑后,行尾符为CRLF(即回车和换行,\r\n)…...
【Redis】Redis入门以及什么是分布式系统{Redis引入+分布式系统介绍}
文章目录 介绍redis的引入 分布式系统单机架构应用服务和数据库服务分离【负载均衡】引入更多的应用服务器节点 单机架构 分布式是什么 数据库分离和负载均衡 理解负载均衡 数据库读写分离 引入缓存 数据库分库分表 引入微服务 介绍 The open source, in-memory data store us…...
C#高级:常用的扩展方法大全
1.String public static class StringExtensions {/// <summary>/// 字符串转List(中逗 英逗分隔)/// </summary>public static List<string> SplitCommaToList(this string data){if (string.IsNullOrEmpty(data)){return new List&…...
Consul持久化配置报错1067---consul_start
报错都是文件写的有问题或者格式问题,直接复制我的这个改改地址就行 先创建文本文件consul_start.txt--->再复制代码保存---->再把.txt改成.bat 持久化存储的地址在:mydata 注:D:\consul\consul_1.20.2_windows_386改成自己consul的…...
「 机器人 」扑翼飞行器控制策略浅谈
1. 研究背景 • 自然界中的蜂鸟以极高的机动能力著称,能够在短至0.2秒内完成如急转弯、快速加速、倒飞、躲避威胁等极限机动。这种表现对微型飞行器(Flapping Wing Micro Air Vehicles, FWMAVs)具有重要的仿生启示。 • 目前的微型飞行器距离自然生物的飞行能力仍有相当差距…...
Qt信号与槽底层实现原理
在Qt中,信号与槽是实现对象间通信的核心机制, 类似于观察者模式。当某个事件发生后,比如按钮被点击,就会发出一个信号(signal)。这种发出是没有目的的,类似广播。如果有对象对这个信号感兴趣,它就会使用连接(connect)函数,将想要处理的信号和自己的一个函数(称为槽…...
QT QTableWidget控件 全面详解
本系列文章全面的介绍了QT中的57种控件的使用方法以及示例,包括 Button(PushButton、toolButton、radioButton、checkBox、commandLinkButton、buttonBox)、Layouts(verticalLayout、horizontalLayout、gridLayout、formLayout)、Spacers(verticalSpacer、horizontalSpacer)、…...
Flutter_学习记录_基本组件的使用记录
1.TextWidge的常用属性 1.1TextAlign: 文本对齐属性 常用的样式有: TextAlign.center 居中TextAlign.left 左对齐TextAlign.right 有对齐 使用案例: body: Center(child: Text(开启 TextWidget 的旅程吧,珠珠, 开启 TextWidget 的旅程吧&a…...
基于JAVA的微信点餐小程序设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
计算机毕业设计hadoop+spark+hive民宿推荐系统 酒店推荐系统 民宿价格预测 酒店价格 预测 机器学习 深度学习 Python爬虫 HDFS集群
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...
Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目
应用场景: 1、常规某个机器被钓鱼后门攻击后,我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后,我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
RabbitMQ 各类交换机
为什么要用交换机? 交换机用来路由消息。如果直发队列,这个消息就被处理消失了,那别的队列也需要这个消息怎么办?那就要用到交换机 交换机类型 1,fanout:广播 特点 广播所有消息:将消息…...
【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...
Qt学习及使用_第1部分_认识Qt---Qt开发基本流程
前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...
