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

动态规划之最长上升子序列模板

今天开始更新动态规划的模板(动态规划哪有模板呀!!!)话是这么说,但我们经常做题会发现有些题目有些共性,我们抽取共性总结出来,应付动态规划基础题目还是可以的。

回归正题,我们今天使用(nlogn),时间复杂度来写,模板主要使用Java来写(为什么不用c语言呢,因为c语言的模板太多了呀!!!)

我们解释一下原理吧,我们在求最长上升子序列时,可以秉持着尽量使得结尾的数最小的思想,其实也就是贪心,谁让这个贪心比n的平方的普通动规要低时间复杂度呢。我们开个ArrayList不断往里加数字,如果链表为空就直接加入,不为空,如果加入的数字大于链表尾数字,我们加入到链表末端,如果加入的数字小于链表的末尾数字,我们把它找到在链表中第一个大于它的元素的位置,把它替换为我们要加入的元素。在这里我们使用写好的二分方法,大家要注意我们求的是上升子序列不是不下降子序列,一旦我们在ArrayList里边发现一个和我们加入的数字相同的数字,我们必须

放弃加入。

模板题目:

夏令营:动态规划特训 - 【算法模板题】蓝桥勇士 - 蓝桥云课 (lanqiao.cn)

模板:


import java.awt.FontFormatException;
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
public class Main {public static void main(String[] args) throws IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
int a=sc.nextInt();
int b;
ArrayList<Integer> al1=new ArrayList<>();
for(b=0;b<a;b++) {int c=sc.nextInt();if(al1.size()==0) {al1.add(c);}if(c>al1.get(al1.size()-1)) {al1.add(c);}else {int d=Collections.binarySearch(al1,c);if(d<0) {int e=(-1)*d-1;al1.set(e, c);}}
}
System.out.println(al1.size());}}

相关文章:

动态规划之最长上升子序列模板

今天开始更新动态规划的模板&#xff08;动态规划哪有模板呀&#xff01;&#xff01;&#xff01;&#xff09;话是这么说&#xff0c;但我们经常做题会发现有些题目有些共性&#xff0c;我们抽取共性总结出来&#xff0c;应付动态规划基础题目还是可以的。 回归正题&#xf…...

Python源码05:使用Pyecharts画词云图图

**Pyecharts是一个用于生成 Echarts 图表的 Python 库。Echarts 是一个基于 JavaScript 的数据可视化库&#xff0c;提供了丰富的图表类型和交互功能。**通过 Pyecharts&#xff0c;你可以使用 Python 代码生成各种类型的 Echarts 图表&#xff0c;例如折线图、柱状图、饼图、散…...

MariaDB 10.11.4 安装教程(zip格式,Windows环境)

前言 MariaDB 10.11.4 这个版本是目前最新的长期支持版&#xff0c;下面来安装下 下载 官网&#xff1a;MariaDB 10.11.4 打开上面链接&#xff0c;点Download 安装 解压缩下载的 zip 文件&#xff0c;到 bin 目录&#xff0c;管理员运行cmd&#xff0c;执行如下命令 mys…...

【Python国内源】pip换源终极方法【Windows】

1、为什么要pip换源下载 安装第三方库时&#xff0c;很多库来自于国外&#xff0c;下载速度慢得感人&#xff01; 2、常见的国内源 https://pypi.tuna.tsinghua.edu.cn/simple #清华 http://mirrors.aliyun.com/pypi/simple/ #阿里云 https://pypi.mirrors.ustc.e…...

【elementUi】绘制自定义表格、绘制曲线表格

要求绘制下图系列表格&#xff1a; 实现步骤: 1.绘制树&#xff0c;实现树勾选字段—>表格绘制字段 逻辑&#xff1a; 树&#xff1a;check-change“treeChart.handleCheckChange” 绑定点击选择事件&#xff0c;改变data.column3数据项&#xff1b;表格:columns"data…...

使用 Python 中的 Langchain 从零到高级快速进行工程

大型语言模型 (LLM) 的一个重要方面是这些模型用于学习的参数数量。模型拥有的参数越多,它就能更好地理解单词和短语之间的关系。这意味着具有数十亿个参数的模型有能力生成各种创造性的文本格式,并以信息丰富的方式回答开放式和挑战性的问题。 ChatGPT 等法学硕士利用 T...

神经网络基础-神经网络补充概念-07-使用计算图求导

步骤 定义计算节点和操作&#xff1a; “x” 是输入变量。 “Add” 表示加法操作。 “Sub” 表示减法操作。 “Multiply” 表示乘法操作。 计算函数值&#xff1a; 首先&#xff0c;我们将 x0 的值代入计算图中&#xff0c;计算出函数的值。 反向传播计算导数&#xff1a; 我…...

docker常用指令

一、Docker指令 1、启动Docker &#xff1a;systemctl start docker 2、查看Docker状态:systemctl status docker 状态为active表示正在运行中 3、停止运行Docker:systemctl stop docker 4、重启Docker:systemctl restart docker 5、开机启动Docker:systemctl enable docker 二…...

【金融量化】对企业进行估值的方法有哪些?

估值的方法有哪些&#xff1f; 如何对企业进行估值&#xff1f;有2个方法估算。 1 绝对估值法 它是一种定价模型&#xff0c;用于计算企业的内在价值。 比如说你可以根据公司近N年的现金流情况。借此去预测未来N年的现金流情况。所有的现金流数据都可以在年报上查询到。最后…...

Qt+C++自定义控件仪表盘动画仿真

程序示例精选 QtC自定义控件仪表盘动画仿真 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对<<QtC自定义控件仪表盘动画仿真>>编写代码&#xff0c;代码整洁&#xff0c;规则&…...

怎样让音频速度变慢?请跟随以下方法进行操作

怎样让音频速度变慢&#xff1f;在会议录音过程中&#xff0c;经常会遇到主讲人语速过快&#xff0c;导致我们无法清晰听到对方说的内容。如果我们能够减慢音频速度&#xff0c;就能更好地记录对方的讲话内容。此外&#xff0c;在听到快速播放的外语或方言时&#xff0c;我们也…...

【C语言】常用的库和作用以及对应的函数

常规编程时&#xff1a; <stdio.h>&#xff1a;提供标准输入输出函数&#xff0c;例如printf、scanf、fprintf、fscanf等。 <stdlib.h>&#xff1a;提供常用的通用函数&#xff0c;例如内存管理函数&#xff08;malloc、calloc、realloc、free&#xff09;、随机数…...

Android 12.0 系统systemui下拉通知栏的通知布局相关源码分析

1.前言 在android12.0的系统rom开发中,在进行systemui中的下拉通知栏的布局自定义的时候,对于原生systemui的 系统的下拉通知栏的通知布局的了解也是非常重要的,接下来就来分析下相关的下拉通知栏的通知布局的相关 源码流程,了解这些才方便对通知栏的布局做修改 2.系统sy…...

java实现docx,pdf文件动态填充数据

一&#xff0c;引入pom 根据需求引入自己所需pom org.apache.poi poi 4.1.1 org.apache.poi poi-ooxml 4.1.1 org.jxls jxls 2.6.0 ch.qos.logback logback-core org.jxls jxls-poi 1.2.0 fr.opensagres.xdocreport fr.opensagres.xdocreport.core 2.0.2 fr.opensagres.xdocrep…...

【Python2】实现异步进程的创建、终止与资源回收

章节索引 前言〇、问题与难点一、进程、异步进程、线程 / 进程池二、最终的代码构成三、代码逻辑讲解四、扩展的知识后记 前言 由于业务需求&#xff0c;需要在服务中加入一个异步任务&#xff0c;执行大量的耗时计算操作&#xff0c;需求细节如下&#xff1a; Handler处理器…...

leetcode做题笔记79单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻”单元格是那些水平相邻或垂直相…...

http库 之 OKHttpUtil

源码位置 方便实用&#xff0c;个人感觉不错 依赖 <dependency><groupId>io.github.admin4j</groupId><artifactId>common-http-starter</artifactId><version>0.7.5</version> </dependency>代码实践 /*** 通用http的pos…...

gitlab合并新项目和分支切换

一、新建项目 1、创建空白项目 2、先创建一个群组 3、编写群组信息 4、创建群组完成以后新建项目 ​​​​​​​ 二、将代码推送到gitlab 1、初始化 git init 2、关联gitlab地址 # 比如:http://192.168.139.128:7070/cloud/obwt_cloud.git git remote add origin <你…...

WebStorm修改默认打开的浏览器

有两种方式第一种修改系统默认浏览器 我采用的是下面这种&#xff0c;在webstorm中修改 将浏览器设置为默认的浏览器即可...

vue3+vite+pinia

目录 一、项目准备 1.1、Vite搭建项目 1.2、vue_cli创建项目 二、组合式API(基于setup) 2.1、ref 2.2、reactive 2.3、toRefs 2.4、watch和watchEffect 2.5、computed 2.6、生命周期钩子函数 2.7、setup(子组件)的第一个参数-props 2.8、setup(子组件)的第二个参数…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...