【dp】最长递增子序列
文章目录
- 方法一:动态规划
- 方法二:贪心 + 二分查找
- 构造最长递增子序列

方法一:动态规划
- dp[i]:末尾元素为arr[i]的最长子序列的长度

从0遍历到i - 1,若遍历到的元素小于当前值arr[i],表示当前值arr[i]可以和前面的某个值组成递增序列,则尝试更新dp[i]
int LIS(vector<int>& arr) {int n = arr.size();if(n == 0) return 0;vector<int> dp(n, 1);int ans = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(arr[j] < arr[i]){dp[i] = max(dp[i], dp[j] + 1);}}ans = max(ans, dp[i]);}return ans;
}
时间复杂度: O ( N 2 ) O(N^2) O(N2)
方法二:贪心 + 二分查找
我们考虑维护一个数组 min_tails,min_tails[i]表示长度为i + 1的递增子序列末尾元素的最小值,min_tails并不是记录arr中的递增子序列

看最后一个g数组,g[2]=3,表示长度为3的递增子序列末尾的最小值为3。长度为3的递增子序列有[1,6,7]、[1,2,4]、[1,2,5]、[1,2,3]
为什么min_tails数组中要维护各个不同长度递增子序列末尾元素的最小值呢?
min_tails数组中维护各个不同长度递增子序列末尾元素的最小值时,arr的后续元素可以和不同长度子序列末尾的最小值比较,从而确定后续元素可以加入哪个子序列,成为新的递增子序列

int LIS(vector<int>& arr) {int n = arr.size();if(n == 0) return 0;vector<int> tails(n);min_tails[0] = arr[0];int len = 1;for(int i = 1; i < n; i++){// 如果当前元素比长度为len的子序列末尾元素的最小值大,说明当前元素可以和长度为len的子序列组成新的递增子序列if(min_tails[len - 1] < arr[i]){min_tails[len] = arr[i];len++;continue;}// 二分:用arr[i]更新tails中最靠左侧的大于arr[i]的值int l = 0;int r = len;while(l < r){int mid = l + (r - l) / 2;if(min_tails[mid] < arr[i]) l = mid + 1; // 用l找第一个比arr[i]大的值,也可以找最后一个小于等于arr[i]的值else r = mid;}min_tails[l] = arr[i];}return len;
}
构造最长递增子序列

max_len相同时取最小的,ans初始化为len个元素,从后往前填写。如果max_len相同,靠后的arr[i]一定更小,若靠后的arr[i]更大,那max_len就不能相同了。比如:

class Solution {
public:vector<int> LIS(vector<int>& arr) {int n = arr.size();if(n < 2) return arr;vector<int> min_tails(n); // min_tails[i]:长度为i+1的最长递增子序列末尾元素的最小值min_tails[0] = arr[0];int len = 1; // 当前最长递增子序列的长度vector<int> max_len(n); // max_len[i]:表示以arr[i]结尾的最长递增子序列的长度max_len[0] = 1;for(int i = 1; i < n; i++){// 当前元素arr[i]已经比当前最长递增子序列末尾元素的最小值要大,说明可以和当前递增子序列组成新的递增子序列if(arr[i] > min_tails[len - 1]){min_tails[len] = arr[i];max_len[i] = len + 1; // arr[i]可以增加最长递增子序列的长度len++;continue;}// arr[i]不能和当前最长递增子序列组成新的递增子序列,可以尝试用arr[i]和较短的递增子序列组成新的递增子序列(极端情况下,arr[i]自己组成长度为1的递增子序列)// 在[l, r)之间找第一个大于arr[i]的位置,说明arr[i]可以和前面较短的递增子序列组成新的递增子序列,用arr[i]更新第一个大于arr[i]的元素,即让某递增子序列的长度不变,而末尾元素变小int l = 0;int r = len;while(l < r){int mid = l + (r - l) / 2;if(min_tails[mid] < arr[i]) l = mid + 1;else r = mid; // 不能是r = mid - 1,因为要找第一个大于arr[i]的值,此时min_tails[mid] >= arr[i],r = mid - 1会跳过大于arr[i]的min_tails[mid]}min_tails[l] = arr[i];max_len[i] = l + 1; // arr[i]不能增加最长递增子序列的长度,min_tails[l]是第一个大于arr[i]的元素,即用arr[i]可以组成长度为l + 1的递增子序列}vector<int> ans(len);int idx = len - 1;// 只能按顺序填for(int i = n - 1; i >= 0; i--){// 遍历max_len数组,最大长度为idx + 1时才可填写ans[idx],max_len相同时必然取最靠后的arr[i],因为最靠后的最小if(max_len[i] == idx + 1){ans[idx] = arr[i];idx--;}}return ans;}
};
相关文章:
【dp】最长递增子序列
文章目录 方法一:动态规划方法二:贪心 二分查找构造最长递增子序列 方法一:动态规划 dp[i]:末尾元素为arr[i]的最长子序列的长度 从0遍历到i - 1,若遍历到的元素小于当前值arr[i],表示当前值arr[i]可以和…...
docker容器:Docker-Compose
目录 一、Docker-Compose 1、Docker-Compose使用场景 2、Docker-Compose简介 3、Docker-Compose安装部署 4、YML文件编写注意事项 5、Compose配置常用字段 6、 Docker Compose 常用命令 7、Docker Compose 文件结构 8、docker Compose撰写nginx 镜像 9、docker Compos…...
如何使用DNS实现融合CDN功能
将托管DNS解决方案与CDN配对可为您的网站提供额外的性能、可靠性和灵活性。 域名系统(DNS)是一种用于计算机、服务或连接到Internet或专用网络的任何资源的分层分布式命名系统,它将各种信息与分配给每个参与实体的域名相关联,它基…...
有关实现深拷贝的四种方法
深拷贝与浅拷贝: 在开始之前我们需要先了解一下什么是浅拷贝和深拷贝,其实深拷贝和浅拷贝都是针对的引用类型,JS中的变量类型分为值类型(基本类型)和引用类型;对值类型进行复制操作会对值进行一份拷贝,而对…...
Mysql 高可用部署实践
mysql主从是如何备份的? 在MySQL主从复制架构下,备份通常需要在主库和从库上分别进行。 主库备份: 在主库上进行备份时,可以使用mysqldump等命令生成SQL文件,并将其保存到本地或者远程服务器上。备份过程中需要注意以下几点&a…...
IEEE-TMI:张孝勇团队开发小鼠精细脑结构自动分割的深度学习算法
近日,复旦大学类脑智能科学与技术研究院青年研究员张孝勇课题组联合德国亥姆霍兹慕尼黑研究中心,在医学图像处理领域顶尖期刊《IEEE医学影像汇刊》(IEEE Transactions on Medical Imaging,TMI) 发表了题为《MouseGAN:用于小鼠大脑…...
八股文之面向对象和面向过程的区别
面向对象(Object-Oriented)和面向过程(Procedural)是两种不同的编程思想。 面向过程是以任务为中心,将程序分解成一系列步骤,在每个步骤中定义一个函数来完成特定的任务。它主要关注程序执行的过程和如何组…...
SpringBoot使用Redis实现分布式缓存
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
Three——二、加强对三维空间的认识
Three——二、加强对三维空间的认识 接上个例子我们接着往下看 辅助观察坐标系 THREE.AxesHelper()的参数表示坐标系坐标轴线段尺寸大小,你可以根据需要改变尺寸。 使用方法: // AxesHelper:辅助观察的坐标系 const axesHelper new THRE…...
【Java】Java8接口中方法区别和使用
Java接口说明 jdk1.8之前接口只能是抽象方法。实现接口必须重写所有方法,比较麻烦。在java8中,支持default和static方法,这样,实现接口时,可以选择是否对default修饰的方法重写。 抽象方法 接口当中的抽象方法&#x…...
WPF 控件库Live Charts 折线图多折线比较问题处理
使用Live Charts功能对比多条折线时当Label不是一一对应时会发现折线无法对比如 Labels List<double> list2 new List<double>(); list2.Add(2.1); //x为0.5时 list2.Add(2.2); //x为0.6时 …...
接口优化方案
前言 最近随着国产化热潮,公司的用于营业的电脑全部从windows更换成了某国产化电脑,换成国产化之后,我们系统的前台web界面也由之前的jsp页面重构成vue.所以之前的一体式架构也变成了前后端分离的架构。但是在更换过程后,发现一些…...
《商用密码应用与安全性评估》第二章政策法规2.1网络空间安全形式与商业密码工作
一、国际国内网络空间安全形势 网络空间已成为与陆地、海洋、天空、太空同等重要的人类第五空间。 1.国际形势 网络空间安全纳入国家战略 网络攻击在国家对抗中深度应用 网络空间已逐步深入网络底层固件 2.国内形势 核心技术仍受制于人 信息产品存在巨大安全隐患 关…...
C#实现将文件、文件夹压缩为压缩包
C#实现将文件、文件夹压缩为压缩包 一、C#实现将文件、文件夹压缩为压缩包核心 1、介绍 Title:“基础工具” 项目(压缩包帮助类) Description步骤描述: 1、创建 zip 存档,该文档包含指定目录的文件和子目录…...
程序员跳槽,要求涨薪50%过分吗?
如果问在TI行业涨工资最快的方式是什么? 回答最多的一定是:跳槽! 前段时间,知乎上这样一条帖子引发了不少IT圈子的朋友的讨论 ,有网友提问 “程序员跳槽要求涨薪50%过分吗?” 截图来源于知乎,…...
Java核心技术 卷1-总结-10
Java核心技术 卷1-总结-10 通配符类型通配符概念通配符的超类型限定无限定通配符通配符捕获 通配符类型 通配符概念 通配符类型中,允许类型参数变化。 例如,通配符类型Pair<? extends Employee>表示任何泛型Pair类型,它的类型参数是…...
React Props
state 和 props 主要的区别在于 props 是不可变的,而 state 可以根据与用户交互来改变。 所以,有些容器组件需要定义 state 来更新和修改数据。 而子组件只能通过 props 来传递数据。 props 使用 Demo.js : import React from reactfunct…...
【Hello Network】协议
作者:小萌新 专栏:网络 作者简介:大二学生 希望能和大家一起进步 本篇博客简介:简单介绍下协议并且设计一个简单的网络服务器 协议 协议的概念结构化数据传输序列化和反序列化网络版计算机服务端代码协议定制客户端代码服务线程执…...
零项目零科研,本科排名倒数,一战上岸上海交大电子与通信工程
笔者来自通信考研小马哥23上交819全程班学员 本科就读于哈工大(威海),本科成绩很差,专业排名62/99,没有科研,没有实验室,没有项目,连最基本大家都会参加的科技立项我四年也没有参与…...
NOIP模拟赛 T3区间
题目大意 有 n n n个数字,第 i i i个数字为 a i a_i ai。有 m m m次询问,每次给出 k i k_i ki个区间,每个区间表示第 l i , j l_{i,j} li,j到第 r i , j r_{i,j} ri,j个数字,求这些区间中一共出现了多少种不同的数字。部…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
