当前位置: 首页 > news >正文

【动态规划】最长上升子序列(单调队列、贪心优化)

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

 

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:最长上升子序列

题解:

代码实现:

完结撒花:


本篇是对最长上升子序列基础做法的一种优化,没有看过基础做法的uu们可以看看这篇:最长上升子序列 

题目:最长上升子序列

题解:

优化的做法与之前相比,适用范围更广,当数据范围大的时候,基础做法会TLE。

但优化做法Dp的思想却少了,更像是一种贪心,由于本题是从DP衍生出来的,所以仍然将其归为DP。

废话不多说。

朴素做法为,找到前一个小于当前值,将其最长上升子序列加一,就为当前值得最长上升子序列。

但观察每一个被插入得值,例如有以下五个数字

3和1都为上升序列为1的数组,但能插入到1上的一定能插到三的上面,反之却不一定。所以我们可以想象出,只要保存上升序列长度中最小的那个值最为末端就可以了。

例如这里的3和1都为长度为1的上升序列,但我们只要保存1.

 

之后再将2插入到1上,此时更新上升序列长度为2的最后一个值为2.

4又可以插入到2后,所以更新长度为3的最后一个值为4。

 

最后如图所示

所以我们很容易就能归纳出上面的过程,找到最大小于待插入数的序列,在下一个位置更新其序列长度与队尾的值。

分析下代码实现,len为当前最长的子序列,利用二分查找寻找,最大的小于当前值x的位置,之后将下一个最长子序列的末位更新为x。循环往复即可

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int q[N];int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];}int len=0;q[0]=-2e9;for(int i=0;i<n;i++){int l=0,r=len;while(l<r){int mid=l+r+1>>1;if(q[mid]<a[i])l=mid;else r=mid-1;}len=max(len,r+1);q[r+1]=a[i];}cout<<len;return 0;
}

完结撒花:

🌈本篇博客的内容【动态规划:最长上升子序列(单调队列、贪心优化)】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

相关文章:

【动态规划】最长上升子序列(单调队列、贪心优化)

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

海思SD3403/SS928V100开发(7)mcp2515-SPI转CAN驱动开发

1. 前言 需求: 需要一路can进行收发 分析: 根据目前使用较多的方案是使用主控端SPI接口 接入MCP2515芯片进行CAN协议转换 硬件: MCP2515->SPI2->SS928 2. Uboot开发 2.1 pinmux复用配置 2.1.1 修改uboot参数表 路径: osdrv/tools/pc/uboot_tools/ SS928V100…...

【安卓源码】SurfaceFlinger 启动及其与应用通信

1. surfaceFlinger 初始化和消息队列处理机制 surfaceflinger 的makefile 文件 /frameworks/native/services/surfaceflinger/Android.bp 235 cc_binary { 236 name: "surfaceflinger", 237 defaults: ["libsurfaceflinger_binary"], 238 i…...

springboot车辆充电桩

sprinboot车辆充电桩演示录像2022开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;ecli…...

linux进程和进程通信编程(1)

What makes the desert beautiful is that somewhere it hides a well. 沙漠之所以美丽,是因为在它的某个角落隐藏着一口井. linux进程和进程通信编程&#xff08;1&#xff09;1.什么是进程2.进程id(pid)3.进程间通信的方法管道信号IPCSocket4.创建进程forkfork有三个返回值父…...

操作系统(1.3)--习题

一、课堂习题 1、一个作业第一 次执行时用了5min ,而第二次执行时用了6min,这说明了操作系统的( )特点。 A、并发性 B、共享性 C、虚拟性 D、不确定性 D 2、在计算机系统中,操作系统是( )。 A、处于裸机之上的第一层软件 B、处于硬件之下的低层软件 C、处于应用软件之上的系统软…...

刷题笔记之十三(有假币、最难的问题、因子个数)

目录 1. 求正数数组的最小不可组成和 2. 有假币 3. 继承时先调用父类的构造方法;类中的成员变量的初始化操作都在构造方法时进行 4. 学会并理解装箱拆箱,注意new出来的也可以拆!! 5. getDeclaredMethods()是标识类或接口的声明成员(这个表示public private 包访问权限 pro…...

5个代码技巧,加速你的Python

5个代码技巧&#xff0c;加速你的Python 人生苦短&#xff0c;快学Python&#xff01; Python作为一种功能强大的编程语言&#xff0c;因其简单易学而受到很多初学者的青睐。它的应用领域又非常广泛&#xff1a;科学计算、游戏开发、爬虫、人工智能、自动化办公、Web应用开发…...

字节跳动软件测试岗,前两面过了,第三面HR天坑!竟然跟我说……

阎王易见&#xff0c;小鬼难缠。我一直相信这个世界上好人居多&#xff0c;但是也没想到自己也会在阴沟里翻船。我感觉自己被字节跳动的HR坑了。在这里&#xff0c;我只想告诫大家&#xff0c;offer一定要拿到自己的手里才是真的&#xff0c;口头offer都是不牢靠的&#xff0c;…...

[数据分析与可视化] Python绘制数据地图1-GeoPandas入门指北

本文主要介绍GeoPandas的基本使用方法&#xff0c;以绘制简单的地图。GeoPandas是一个Python开源项目&#xff0c;旨在提供丰富而简单的地理空间数据处理接口。GeoPandas扩展了Pandas的数据类型&#xff0c;并使用matplotlib进行绘图。GeoPandas官方仓库地址为&#xff1a;GeoP…...

ChatGPT加强版GPT-4面世,打工人的方式将被颠覆

&#x1f517; 运行环境&#xff1a;chatGPT&#xff0c;GPT-4 &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 #### 防伪水印——左手の明天 #### &#x1f497; 大家好&#…...

Python逆向及相关知识

今天第二次看见python字节码的逆向题&#xff0c;然后发现了一个介绍Python逆向的文章&#xff0c;所以把文章里的内容简单整理记录一下。 文章参考&#xff1a;https://www.cnblogs.com/blili/p/11799398.html Python运行原理&#xff1a; 一.什么是Python Python 是一种解…...

Python基础语法、注意点加实例全解

本篇文章我们讲解Python最基础语法&#xff0c;包含&#xff1a;数据类型、注释、变量、类型转换、命名规范、运算符、字符串拼接、字符串格式化、if条件判断、while循环、for循环、函数、读取文件、写入文件、异常捕获、包导入等。通过讲解语法注意事项实例代码详解&#xff0…...

ETH RPC搭建

配置选择先是看了aws、谷歌云、阿里云这个配置都要1-2wrmb一个月&#xff0c;太贵了问了很多朋友&#xff0c;打算用hetzner&#xff0c;50欧一个月足以我选的配置&#xff1a;64gb&#xff0c;2tb ssd开好后在邮箱收到信息链接后按以下步骤安装系统&#xff1a;https://0o0.me…...

南京邮电大学数据库第一次课后作业

1.单选题 (5分) (B)是存储在计算机内有结构的数据的集合。 &#xff08;A&#xff09;数据库系统 &#xff08;B&#xff09;数据库 &#xff08;C&#xff09;数据库管理系统 &#xff08;D&#xff09;数据结构 2.单选题 (5分) 数据库的特点之一是数据的共享,严格的讲,这里的…...

近期投简历、找日常实习的一些碎碎念(大二---测试岗)

嘿嘿嘿&#xff0c;我又回来了&#xff0c;相信不少兄弟已经发现我似乎已经断更了好久&#xff0c;哈哈&#xff0c;我是尝试去找实习&#xff0c;投简历面试去了。 先说一下背景。 目录 背景 求职进行中 简历 投递和沟通 收获和感受 背景 博主&#xff0c;大二软件工程…...

ThreadLocal的使用

1. ThreadLocal介绍 ThreadLocal顾名思义&#xff0c;就是线程的本地变量&#xff0c;只有当前线程可见&#xff0c;对其他线程来说是封闭且隔离的。每一个线程为自己本身创建ThreadLocal变量&#xff0c;只有当前线程可以访问&#xff0c;其他的线程不可以&#xff0c;从根源…...

Java ~ Reference【总结】

一 概述 简介 在JDK1.2之前&#xff0c;Java中引用的定义是十分传统的&#xff1a;如果引用类型的变量中存储的数值代表的是另一块内存的起始地址&#xff0c;就称这块内存代表着一个引用。在这种定义之下&#xff0c;一个对象只有被引用和没有被引用两种状态。 实际上&#xf…...

最快方法求最长上升子序列(LIS)+最长公共子序列(LCS)模板(C/C++)

目录 1 LIS算法&#xff08;最长上升子序列&#xff09; 1.1 简介 1.2 代码 1.3 相关解释 2 LCS算法&#xff08;最长公共子序列&#xff09; 2.1 简介 2.2 代码&#xff08;动态规划&#xff0c;时间复杂度O&#xff08;nlogn&#xff09;&#xff09; 2.3 特殊…...

012+limou+C语言深入知识——(4)“结构体”与“枚举体”与“联合体”

一、结构体 1、结构体基础 &#xff08;1&#xff09;结构体完全声明 struct tag {member-list; }variable-list;//描述一个人 struct people {char name[10];//人名int age;//年龄int idnumber;//身份证 };&#xff08;2&#xff09;结构体不完全声明&#xff08;匿名结构体…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...