最长不下降子序列LIS详解

最长不下降子序列指的是在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降(非递减)的。

假如,现有序列A=[1,2,3,-1,-2,7,9](下标从1开始),它的最长不下降子序列是[1,2,3,7,9],长度为5。另外,还有一些子序列是不下降子序列,比如[1,2,3]、[-2,7,9]等,但是都不是最长的。

对于这个问题可以用最原始的方法枚举每一种情况,但是时间复杂度太高。

使用动态规划求解,令dp[i]表示以A[i]结尾的最长不下降子序列长度,这样对A[i]有两种可能:

(1)如果存在A[i]之前的元素A[j](j<i),使得A[j]<=A[i]且dp[j]+1>dp[i](即把A[i]跟在以A[j]结尾的LIS后面时能比当前以A[i]结尾的LIS长度更长),那么就把A[i]跟在以A[j]结尾的LIS后面,形成一条更长的不下降子序列(令dp[i]=dp[j]+1)。

(2)如果A[i]之前的元素都比A[i]大,那么A[i]就只好自己形成一条LIS,但是长度为1,即这个子序列里面只有一个A[i]。

最后以A[i]结尾的LIS长度就是(1)(2)中能形成的最大长度。

由此可以写出状态转移方程:

dp[i]=max\left ( 1,dp[j]+1 \right )

上面的状态转移方程隐含了边界:dp[i]=1,因此只要让i从小到大遍历即可求出整个dp数组。由于dp[i]表示的是以A[i]结尾的LIS长度,因此从整个dp数组中找出最大的那个才是要寻求的整个序列的LIS长度,整体复杂度为O\left ( n^{2} \right )

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int A[N],dp[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>A[i];}int ans=-1;for(int i=1;i<=n;i++){dp[i]=1;//初始条件(即先假设每个元素自成一个子序列) for(int j=1;j<i;j++){if(A[i]>=A[j]&&(dp[j]+1>dp[i])){dp[i]=dp[j]+1;}}ans=max(ans,dp[i]);}cout<<ans;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/350926.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

16.大模型分布式训练框架 Microsoft DeepSpeed

微调、预训练显存对比占用 预训练LLaMA2-7B模型需要多少显存&#xff1f; 假设以bf16混合精度预训练 LLaMA2-7B模型&#xff0c;需要近120GB显存。即使A100/H100&#xff08;80GB&#xff09;单卡也无法支持。 为何比 QLoRA多了100GB&#xff1f;不妨展开计算下显存占用&…

誉天教育近期开班计划(6月15日更新)

云计算HCIP 周末班 2024/6/15 田老师 售前IP-L3 周末班 2024/6/15 陈老师 RHCA442 晚班 2024/6/17邹老师 数通HCIE 晚班 2024/6/24阮老师 云计算HCIE直通车晚班 2024/6/25 曾老师 售前IT-L3 周末班 2024/6/29 伍老师 数通HCIP 晚班 2024/7/1杨老师 存储直通车 晚班 2024/7/1 高…

从ES的JVM配置起步思考JVM常见参数优化

目录 一、真实查看参数 &#xff08;一&#xff09;-XX:PrintCommandLineFlags &#xff08;二&#xff09;-XX:PrintFlagsFinal 二、堆空间的配置 &#xff08;一&#xff09;默认配置 &#xff08;二&#xff09;配置Elasticsearch堆内存时&#xff0c;将初始大小设置为…

Windows Server 2008 r2 IIS .NET

Windows Server 2008 r2 IIS .NET

CleanMyMacX4.15.4如何优化苹果电脑系统缓存,告别MacBook卡顿,提升mac电脑性能

你是否曾为苹果电脑存储空间不够而烦恼&#xff1f;是否曾因系统运行缓慢而苦恼&#xff1f;别担心&#xff0c;今天我要给大家种草一个神器——CleanMyMac&#xff01;这款软件可以帮助你轻松解决苹果电脑的种种问题&#xff0c;让你的电脑焕然一新&#xff01; 让我来给大家介…

springboot原理篇-配置优先级

springboot原理篇-配置优先级&#xff08;一&#xff09; springboot项目一个支持三种配置文件 application.propertiesapplication.ymlapplication.yaml 其中&#xff0c;优先级的顺序是&#xff1a; application.properties > application.yml > application.yaml 也…

基于Nios-II实现流水灯

基于Nios-II实现流水灯的主要原理 涉及到FPGA&#xff08;现场可编程门阵列&#xff09;上的嵌入式软核处理器Nios II与LED控制逻辑的结合。以下是详细的实现原理&#xff0c;分点表示并归纳&#xff1a; Nios II软核处理器介绍&#xff1a; Nios II是Altera公司推出的一种应用…

Vue笔记(二)

Vue&#xff08;一&#xff09;&#xff1a;Vue笔记&#xff08;一&#xff09;-CSDN博客 目录 综合案例&#xff1a;水果购物车 生命周期 1.生命周期&生命周期四个阶段 2.生命周期函数&#xff08;钩子函数【8个】&#xff09; 3.生命周期两个案例 初始化渲染 自动获…

Node.js和npm的安装及配置

Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞 I/O 的模型。 npm&#xff08;node package manager&#xff09;是一个 Node.js 包管理和分发工具&#xff0c;也是整个 Node.js 社区最流行、支持第三方模块最多的包管理器。使…

2024.6.14 作业 xyt

使用手动连接&#xff0c;将登录框中的取消按钮使用第二中连接方式&#xff0c;右击转到槽&#xff0c;在该槽函数中&#xff0c;调用关闭函数 将登录按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0c…

Unity2D计算两个物体的距离

1.首先新建一个场景并添加2个物体 2.创建一个脚本并编写代码 using UnityEngine;public class text2: MonoBehaviour {public GameObject gameObject1; // 第一个物体public GameObject gameObject2; // 第二个物体void Update(){// 计算两个物体之间的距离float distance Vec…

学习笔记——网络管理与运维——SNMP(SNMP架构)

三、SNMP架构 1、SNMP结构概述 SNMP被设计为工作在TCP/IP协议族上&#xff0c;基于TCP/IP协议工作&#xff0c;对网络中支持SNMP协议的设备进行管理。所有支持SNMP协议的设备都提供SNMP这个统一界面&#xff0c;使得管理员可以使用统一的操作进行管理&#xff0c;而不必理会设…

课设--学生成绩管理系统(一)

欢迎来到 Papicatch的博客 文章目录 &#x1f349;技术核心 &#x1f349;引言 &#x1f348;标识 &#x1f348;背景 &#x1f348;项目概述 &#x1f348; 文档概述 &#x1f349;可行性分析的前提 &#x1f348;项目的要求 &#x1f348;项目的目标 &#x1f348;…

高才通通过后,香港身份证办理

高才通通过后&#xff0c;到香港前需要准备 身份证办理预约&#xff08;流程见下面&#xff09;办理好D签&#xff1a;在入境前&#xff0c;根据入境处给的签证&#xff0c;下载签证并办理港澳通行证D签&#xff08;逗留签&#xff09;携带的文书&#xff1a;港澳通行证&#…

九、BGP路由属性和选路

目录 一、属性分类 1.1、公认属性 1.2、可选属性 二、选路原则 0、丢弃不可达 取值越大越优 1、Preferred-Value 2、Local_Preference 取值越小越优 3、路由优先级 4、AS_Path 5、Origin 6、MED 7、路由来源 8、Next_Hop的IGP度量值 BGP路由等价负载分担&#…

音频处理软件adobe audition使用教程

教程1笔记 基本操作 点击文件-》新建-》多轨会话&#xff1a; 编辑-》首选项&#xff0c;设置自动保存时间&#xff1a; 导入素材&#xff0c;文件-》导入素材&#xff0c;或者直接拖动进来文件&#xff01; 导出多轨混音&#xff1a; 更改为需要导出的格式wav,mp3等格式&am…

探索开源世界:2024年值得关注的热门开源项目推荐

文章目录 每日一句正能量前言GitCode成立背景如何使用GitCode如何把你现有的项目迁移至 GitCode&#xff1f;热门开源项目推荐actions-poetry - 管理 Python 依赖项的 GitLab CI/CD 工具项目概述技术分析应用场景特点项目地址 Spider - 网络爬虫框架项目简介技术分析应用场景项…

餐厅点餐系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;商品管理&#xff0c;用户管理&#xff0c;店家管理&#xff0c;广告管理 店家账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;商品管理&#xff0c;广告管…

机器学习:GANs网络在图像和视频技术中的应用前景

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…

Qt creator day2练习

使用手动连接&#xff0c;将登录框中的取消按钮使用第二种方式&#xff0c;右击转到槽&#xff0c;在该函数中&#xff0c;调用关闭函数&#xff0c;将登录按钮使用Qt4版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为“admin”&#xff0c;密…