最长上升子序列LIS(一般+优化)
1. 题目
题目链接:
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

输入样例:
6
1 2 4 1 3 4
输出样例:
4
说明/提示:
分别取出 1、2、3、4 即可。
2. 具体实现
2.1 一般做法
dp[i]表示第i个位置的最长上升子序列个数
//思路:
//dp[i]表示第i个位置的最长子序列个数
//dp[i]也就是找到前面1到i-1位置上值小于a[i]的最大dp值
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],dp[N];
int main(void){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}int res=1;for(int i=2;i<=n;i++){int tmax=0;for(int j=1;j<i;j++){ //遍历前i-1项,找到值<a[i]的最大dp值 if(a[i]>a[j]) tmax=tmax>dp[j]?tmax:dp[j];}dp[i]=tmax+1;res=max(res,dp[i]);}cout<<res; return 0;
}
- 时间复杂度: O(n^2)
- 空间复杂度: O(N)
2.2 优化
dp[i]表示最长子序列长度为i的最小尾数
//思路2:
//dp[i]表示最长上升子序列长度为i的最小尾数
//显而易见,dp是一个递增序列
//我们对每一个数进行遍历
//每一次找到值大于a的位置进行更新即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10; //最小尾数最大页只能为1e6
int dp[N];
int a[5010];
int main(void){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1]=a[1]; //初始化 int ans=1;for(int i=1;i<=n;i++){//找到dp中值第一个大于a[i]的位置int t=lower_bound(dp+1,dp+1+ans,a[i])-dp; dp[t]=a[i];ans=max(ans,t);}cout<<ans; return 0;
}
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)
lower_bound()函数是C++提供的二分查找的函数,具体使用方法可以看以下文章:
关于lower_bound( )和upper_bound( )的常见用法_lowerbound和upperbound-CSDN博客
代码自己写的,有什么问题欢迎指正。
都看到这里了,点个赞再走吧!!!(*^_^*)
相关文章:
最长上升子序列LIS(一般+优化)
1. 题目 题目链接: B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 输入样例: 6 1 2 4 1 3 4 输出样例: 4 说明/提示: 分别取出 1、2、3、4 即可。 2. 具体实现 2.1 一般做法 dp[i]表示第i个位置的…...
【Python系列】Python 协程:并发编程的新篇章
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
详解C/C++输入输出
前言 C/C输入输出很多,在不同的情况会用不同的输入输出,有的题目在输入时可能换一种输入输出就能不会TLE,有的输入可能要循环输入,但是可以换一种输入直接就能把所有数据输入进去。C/C有哪些常用的输入输出,在什么时候…...
AI人工智能开发环境配置
AI人工智能 为什么使用Python来开发AI 人工智能被认为是未来的趋势技术。 已经有了许多应用程序。 因此,许多公司和研究人员都对此感兴趣。 但是这里出现的主要问题是,在哪种编程语言中可以开发这些 AI 应用程序? 有各种编程语言,…...
Tomcat 8.5 下载、安装、启动及各种问题
🥰🥰🥰来都来了,不妨点个关注叭! 👉博客主页:欢迎各位大佬!👈 本期内容主要介绍 Tomcat 8 的安装,以及可能会遇到的问题 文章目录 1. Tomcat 安装2. 可能会遇到的问题2.…...
Harbor系列之5:复制管理
Harbor的镜像复制功能 Harbor 提供镜像复制功能,允许用户以推送和拉取方式在不同 Harbor 仓库之间,以及 Harbor 与非 Harbor 仓库间(如Alibaba ACR、Quay、Aws ECR、Azu热ACR、Docker Registry、Docker Hub等)复制 image、chart …...
V.PS德国VPS详细测评
V.PS的德国机房位于法兰克福,默认接入电信CN2 GIA、联通CUII网络,针对中国大陆进行路由优化处理的。而且是强制移动走联通的CUII链路,确保三网都处在轻负载的网络环境下。 CPU是Intel Xeon Gold 6133 ,启用了BBR,归属德…...
【Vue3】组件通信之自定义事件
【Vue3】组件通信之自定义事件 背景简介开发环境开发步骤及源码总结 背景 随着年龄的增长,很多曾经烂熟于心的技术原理已被岁月摩擦得愈发模糊起来,技术出身的人总是很难放下一些执念,遂将这些知识整理成文,以纪念曾经努力学习奋…...
[CTF]-PWN:ORW题型综合解析
经典ORW: 例题(极客大挑战 2019 Not Bad): 这里使用mmap函数创造了一个内存映射区域 从地址0x123000开始,大小位0x1000 权限为可写可执行(可读0x1,可写0x2,可执行0x3)…...
VSCode中yarn的安装和使用
VSCode只要是做前端的,大家都不陌生,就不讲其使用了。 Yarn是一款高效、可靠的JavaScript包管理器,与NPM类似,但有其独特的优势,如更高效的安装速度、更好的依赖管理等 要在VSCode中使用Yarn,需要按照以…...
Java后端面试复习7.23
进程和线程线程优先级线程状态线程构造方式三种推荐用哪种为什么线程中断调用什么方法,本线程怎检查为什么线程不应强制停止线程通信方式四种ThreadLocalFUtureTask线程礼让终止线程的另一个缺陷(锁)守护线程什么时候设置为守护县城sleep&…...
Arduino PID库 (2) –微分导致的过冲
Arduino PID库 (2) – Derivative Kick 参考:手把手教你看懂并理解Arduino PID控制库——微分冲击 pid内容索引-CSDN博客 Arduino PID库 (1)– 简介 问题 此修改将稍微调整derivative term。目标是消除一种称为“…...
基于强化学习算法玩CartPole游戏
什么事CartPole游戏 CartPole(也称为倒立摆问题)是一个经典的控制理论和强化学习的基础问题,通常用于测试和验证控制算法的性能。具体来说,它是一个简单的物理模拟问题,其目标是通过在一个平衡杆(倒立摆&a…...
uniapp0基础编写安卓原生插件和调用第三方jar包(Ch34的jar包)和如何解决android 如何Application初始化
前言 我假设你会uniapp安卓插件开发了,如果不会请看这篇文章,这篇文章是0基础教学。 这篇文章我们将讲一下如何使用CH34XUARTDriver.jar进行开发成uniapp插件。 它的难点是:uniapp如何Application初始化第三方jar包 先去官网下载CH340/CH341的USB转串口安卓免驱应用库:h…...
使用Leaflet进行船舶航行警告区域绘制实战
目录 前言 一、坐标格式转换 1、数据初认识 2、将区域分割成多个点 3、数据转换 4、数据转换调用 二、WebGIS展示空间位置信息 1、定义底图 2、Polygon的可视化 3、实际效果 三、总结 前言 通常而言,海事部门如海事局,通常会在所述的管辖区域内…...
用Ollama 和 Open WebUI本地部署Llama 3.1 8B
说明: 本人运行环境windows11 N卡6G显存。部署Llama3.1 8B 简介 Ollama是一个开源的大型语言模型服务工具,它允许用户在自己的硬件环境中轻松部署和使用大规模预训练模型。Ollama 的主要功能是在Docker容器内部署和管理大型语言模型(LLM&…...
计算机毕业设计选题推荐-学生作业管理系统-Java/Python项目实战
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
RIP实验
实验拓扑: 实验要求: R1-R2-R3-R4-R5:RIP 100 运行版本2 R6-R7:RIP 200 运行版本1 1.使用合理IP地址规划网络,各自创建环回接口 2.R1创建环回 172.16.1.1/24 172.16.2.1/24 172.16.3.1/24 3.要求R3使用R2访问R1环…...
手把手教你如何在宝塔上添加可道云登录页面的ICP备案信息,别跟权威开玩笑。
如何在宝塔上添加可道云登录页面的ICP备案信息 事情的原由来我们开始吧首先登录你的宝塔页面双击打开index.php文件保存退出即可 感谢大佬,希望对被查到的朋友有所帮助! 事情的原由 今天突然收到腾讯云发来的一封Email,说我需要整改我的网站…...
基于JSP技术的大学生校园兼职系统
你好呀,我是计算机学姐码农小野!如果有相关需求,可以私信联系我。 开发语言:JSP 数据库:MySQL 技术:JSPJavaBeans 工具:MyEclipse,Tomcat,Navicat 系统展示 首页 学…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...
