最长上升子序列LIS
发布日期:2021-07-27 13:45:11 浏览次数:1 分类:技术文章

本文共 447 字,大约阅读时间需要 1 分钟。

给定一列数,求最长上升子序列的长度。

O(n^2)的算法大家都会吧。这里介绍一种时间复杂度较低的算法(我也不会算时间复杂度,反正很低)。
我们可以维护一个单调。。。数组吧。若这个数比数组最后一个数大,将它加入数组,长度++;
else替换最早比它大的数。。
讲解就完了,上代码:

#include
#include
#include
using namespace std;int n,m,a[1005],b[1005];int bin(int x){ int l=1,r=m; while(l
b[m]) b[++m]=a[i]; else { int pos=bin(a[i]); b[pos]=a[i]; } } printf("%d\n",m); return 0;}

转载地址:https://blog.csdn.net/Rlt1296/article/details/51901389 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 1798: [Ahoi2009]Seq 维护序列seq
下一篇:洛谷 P1330 封锁阳光大学

发表评论

最新留言

不错!
[***.144.177.141]2024年04月03日 02时02分12秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

基于VMware安装CentOs7的镜像 2019-04-27
PL/SQL数据库管理工具的使用 2019-04-27
带你玩转属于自己的spring-boot-starter系列(一) 2019-04-27
带你玩转属于自己自己的spring-boot-starter系列(二) 2019-04-27
带你玩转属于自己的spring-boot-starter系列(三) 2019-04-27
基于SnowFlake算法如何让分库分表中不同的ID落在同一个库的算法的实现 2019-04-27
基于springboot的ShardingSphere5.X的分库分表的解决方案之分库解决方案(二) 2019-04-27
基于springboot的ShardingSphere5.X的分库分表的解决方案之分表解决方案(一) 2019-04-27
基于springboot的ShardingSphere5.X的分库分表的解决方案之关联查询解决方案(三) 2019-04-27
基于springboot的ShardingSphere5.X的分库分表的解决方案之基于seata的分布式事务的解决方案(十五) 2019-04-27
Linux文件管理参考 2019-04-27
FTP文件管理项目(本地云)项目日报(一) 2019-04-27
FTP文件管理项目(本地云)项目日报(二) 2019-04-27
FTP文件管理项目(本地云)项目日报(三) 2019-04-27
FTP文件管理项目(本地云)项目日报(四) 2019-04-27
【C++】勉强能看的线程池详解 2019-04-27
FTP文件管理项目(本地云)项目日报(五) 2019-04-27
FTP文件管理项目(本地云)项目日报(关于不定长包的测试) 2019-04-27
FTP文件管理项目(本地云)项目日报(六) 2019-04-27
FTP文件管理项目(本地云)项目日报(七) 2019-04-27