优化最长上升子序列

前言:平时我们做的题目都是用动态规划做的,但是有没有能够优化一下呢?

有一个结论,长度为 i 的一个序列,最后一个元素一定是构成长度为 i 的序列中最小的

我们可以用二分来优化


题目地址

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = (int)5e5+10;
int a[N];
int le[N],rig[N];
int n;// 考虑用
signed main(){cin >> n;for(int i=1;i<=n;i++){cin >> a[i];}vector<int> re;le[1] = 1;re.push_back(a[1]);for(int i=2;i<=n;i++){int u = a[i];if(u>=re[re.size()-1]){re.push_back(u);le[i] = re.size();}else{int pos = upper_bound(re.begin(),re.end(),u) - re.begin();re[pos] = u;le[i] = pos + 1; }}re.clear();le[1] = 1;re.push_back(a[n]);for(int i=n-1;i;i--){int u = a[i];if(u>re[re.size()-1]){re.push_back(u);rig[i] = re.size();}else{int pos = upper_bound(re.begin(),re.end(),u) - re.begin();re[pos] = u;rig[i] = pos+1;}}int ans = 0;for(int i=1;i<=n;i++){ans = max(le[i]+rig[i]-1,ans);}cout << ans;system("pause");return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

作为HR如何利用好校园招聘的渠道

对于企业来说校招是个非常不错的招聘渠道&#xff0c;虽然应届生没有工作经验&#xff0c;但是有很多具有高潜能的人才就在其中&#xff0c;他们年轻朝气&#xff0c;学习能力强&#xff0c;稍加培养就可以成为得力顺手的能人。 作为HR绝对要善于运营校招的渠道&#xff0c;如…

微服务_1、入门

文章目录 一、 认识微服务二、 微服务演变2.1、 单体架构2.2、 分布式架构2.3、 微服务2.4、 微服务方案对比 三、 注册中心3.1、 Eureka3.2、 Nacos3.2.1、服务分级存储模型3.2.2、权重配置3.2.3、环境隔离 一、 认识微服务 二、 微服务演变 随着互联网行业的发展&#xff0c;…

ICM20948 DMP代码详解(26)

接前一篇文章&#xff1a;ICM20948 DMP代码详解&#xff08;25&#xff09; 上一回解析完了inv_icm20948_load_firmware函数&#xff0c;回到inv_icm20948_initialize_lower_driver函数中&#xff0c;继续往下进行解析。为了便于理解和回顾&#xff0c;再次贴出inv_icm20948_in…

【黑马点评】已解决java.lang.NullPointerException异常

Redis学习Day3——黑马点评项目工程开发-CSDN博客 问题发现及描述 在黑马点评项目中&#xff0c;进行到使用Redis提供的Stream消息队列优化异步秒杀问题时&#xff0c;我在进行jmeter测试时遇到了重大的错误 发现无论怎么测试&#xff0c;一定会进入到catch中&#xff0c;又由…

ST表(算法篇)

算法篇之ST表 引言&#xff1a;ST表实际是一个数据结构&#xff0c;但是它本质是基于dp算法的&#xff0c;而算法题中有时也会用到&#xff0c;这边我就归类于算法篇先把 ST表 概念&#xff1a; ST表适用于解决区间最值的问题(RMQ问题)的数据结构ST表本质是dp算法&#xff…

【工作流集成】springboot+vue工作流审批系统(实际源码)

前言 activiti工作流引擎项目&#xff0c;企业erp、oa、hr、crm等企事业办公系统轻松落地&#xff0c;一套完整并且实际运用在多套项目中的案例&#xff0c;满足日常业务流程审批需求。 一、项目形式 springbootvueactiviti集成了activiti在线编辑器&#xff0c;流行的前后端…

深度揭秘:日志打印的艺术与实战技巧,让你的代码会说话!

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 &#x1f341;日志&#x1f342;日志分模块实现讲解&#x1f343;日志等级的实现&#x1f965;日志时间*时间的获取* &#x1f308;文…

IntelliJ IDEA 创建 HTML 项目教程

传送门 IntelliJ IDEA 是 JetBrains 提供的一款强大且多功能的集成开发环境&#xff08;IDE&#xff09;&#xff0c;不仅可以用于 Java 开发&#xff0c;还支持多种其他编程语言和技术&#xff0c;包括 HTML、CSS 和 JavaScript 等前端开发工具。本文将带你逐步了解如何使用 …

无人机培训机构必备:驾驶员训练机构合格证技术详解

无人机驾驶员训练机构合格证是针对从事无人机驾驶员培训的机构而设立的资质认证&#xff0c;该证书要求培训机构具备专业的师资力量、完善的教学设施、科学的课程体系以及严格的教学质量监控体系&#xff0c;以确保培训质量和学员安全。以下是对无人机驾驶员训练机构合格证技术…

JavaSE - 面向对象编程02

01 static关键字 01_01 static修饰成员变量 【1】成员变量的分类及特点&#xff1a; ① 类变量&#xff1a;被static修饰&#xff0c;随类一起加载&#xff0c;在计算机中只有一份&#xff0c;被该类的所有对象共享。 ② 实例变量(对象的变量)&#xff1a;不被static修饰&…

Redis命令:redis-cli

Redis 命令用于在 redis 服务上执行操作。 要在 redis 服务上执行命令需要一个 redis 客户端。Redis 客户端在我们之前下载的的 redis 的安装包中。 语法 Redis 客户端的基本语法为&#xff1a; $ redis-cli 实例 以下实例讲解了如何启动 redis 客户端&#xff1a; 启动…

7-ZIP工具的功能分享:合并分卷压缩文件

在日常工作中&#xff0c;有些大文件无法单独传输&#xff0c;我们通常会通过压缩拆分成多个分卷文件来完成传输。 当完成传输后&#xff0c;不想要这么多分卷文件的时候&#xff0c;就可以通过7-ZIP工具的合并功能来解决这个问题。下面一起来看看&#xff0c;具体如何操作。 …

达芬奇竖屏导出有黑屏解决方案

文章目录 项目设置导出设置 初学达芬奇&#xff0c;导出的时候&#xff0c;总是有黑边。 经过研究&#xff0c;才发现导出的时候的分辨率和项目分辨率 2个地方都要设置&#xff0c;否则导出就会导致有黑边。 项目设置 点击 文件 选择项目设置 选择竖屏分辨率 导出设置

基于深度学习,通过病理切片直接预测HPV状态|文献速递·24-09-16

小罗碎碎念 有段时间没有写文献速递的推文了&#xff0c;搞得自己今天写还怪不适应的。 今天所有的推文&#xff0c;都是围绕一个系统的问题展开——既研究了HPV与EBV在头颈癌/鼻咽癌中的致病机制&#xff0c;也总结了如何结合病理组学直接由WSI预测HPV状态——没办法&#x…

SQL注入+CTF实例

SQL注入的做题步骤 1.判断数字型还是字符型 数字型&#xff1a; select * from table where id$id; 字符型&#xff1a; select * from table where id$id; # 一般是单引号闭合&#xff0c;也有可能是双引号&#xff0c;又或者是)、")、))等等都有可能 可以用and 11和an…

【渗透测试】——VulnHub靶机渗透实战 | HA:Joker

&#x1f4d6; 前言&#xff1a;Vulnhub 是一个漏洞靶场平台&#xff0c;里面含有大量的靶场镜像&#xff0c;只需要下载虚拟机镜像&#xff0c;导入 VMWare 或者 VirtualBox 即可启动靶场。本文将从环境搭建、端口扫描、目录扫描到信息提取和突破8080端口&#xff0c;尽可能排…

PMP--一模--解题--101-110

文章目录 11.风险管理--过程--识别风险→实施定性风险分析→实施定量风险分析→规划风险应对→实施风险应对→监督风险101、 [单选] 在项目即将进入收尾阶段时&#xff0c;项目经理发现了一项原来没有考虑到的新风险。该风险一旦发生&#xff0c;可能给最终的可交付成果带来重要…

828华为云征文|Flexus X实例Docker+Jenkins+gitee实现CI/CD自动化部署-解放你的双手~

目录 前言 实验步骤 环境准备 安装Portainer 拉取镜像 更换镜像源 启动容器 安装jenkins 拉取镜像 获取管理员密码 新建流水线项目 Portainer配置 gitee配置WebHooks 构建 修改代码&#xff0c;自动部署 前言 &#x1f680; 828 B2B企业节特惠来袭&#xff0c;…

【自学笔记】支持向量机(2)——核函数

引入 核函数的功能是将一组数据映射到更高维的特征空间&#xff0c;这样可以让在低维无法线性分类的数据能够在高维空间下被分类。   可以证明&#xff0c;如果原始数据是有限的维度&#xff0c;那么一定存在一个高维特征空间使得样本线性可分。 文章内容由《机器学习》相关内…

道路驾驶视角人车检测数据集 16000张 带标注 voc yolo

随着智能驾驶技术和车辆辅助系统的快速发展&#xff0c;道路驾驶视角下的多目标检测成为了保障行车安全的关键技术之一。为了提高自动驾驶车辆以及辅助驾驶系统的性能&#xff0c;需要大量的高质量标注数据来训练这些系统。本数据集旨在为道路驾驶视角下的人车检测提供高质量的…