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

71、最长上升子序列II

最长上升子序列II

题目描述

给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1 ≤ N ≤ 100000 , 1≤N≤100000, 1N100000
− 1 0 9 ≤ 数列中的数 ≤ 1 0 9 −10^9≤数列中的数≤10^9 109数列中的数109

输入样例:7
3 1 2 1 8 5 6输出样例:4

Solution

import java.util.*;class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int N = sc.nextInt();// N 为 100000, n 方的做法会 TLEint[] a = new int[N + 10];// res[i] 数组记录长度为 i 时,所有子序列中结尾最小的元素int[] q = new int[N + 10];// 初始化为 0int len = 0;for(int i = 1; i <= N; i++) {a[i] = sc.nextInt();// 二分查找优化时间复杂度 logn// 查找最后一个小于 a[i] 的值int idx = bsearch(q, len, a[i]);if(idx == len) {len++;q[len] = a[i];}else{if(q[idx + 1] > a[i]) q[idx + 1] = a[i];}}System.out.println(len);}public static int bsearch(int[] q, int n, int x){// 找最后一个小于 x 的位置// 如果都比 x 大的话返回 0// 从 1 到 n 开始二分int low = 1, high = n;while(low <= high){int mid = (low + high) / 2;if(q[mid] < x){if(mid == n || q[mid + 1] >= x) return mid;else low = mid + 1;}else high = mid - 1;}return 0;}
}

相关文章:

71、最长上升子序列II

最长上升子序列II 题目描述 给定一个长度为N的数列&#xff0c;求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数&#xff0c;表示完整序列。 输出格式 输出一个整数&#xff0c;表示最大长度。 数据范围 1 ≤ N ≤ 100000…...

解决必剪电脑版导出视频缺斤少两的办法

背景 前几天将电脑重置了&#xff0c;今天想要剪辑一下视频&#xff0c;于是下载了必剪&#xff0c;将视频、音频都调整好&#xff0c;导出&#xff0c;结果15分钟的视频只能导出很短的时长&#xff0c;调整参数最多也只能导出10分钟&#xff0c;My God&#xff01; 解决 首…...

新人学习笔记之(常量)

一、什么是常量 1.常量&#xff1a;在程序的执行过程中&#xff0c;其值不能发生改变的数据 二、常量的分类 常量类型说明举例整型常量整数、负数、0123 456实型常量所有带小数点的数字1.93 18.2字符常量单引号引起来的字母、数字、英文符号S B字符串常量双引号引起来的&…...

Lua解释器裁剪

本文目录 1、引言2、文件功能3、选择需要初始化的库4、结论 文章对应视频教程&#xff1a; 已更新。见下方 点击图片或链接访问我的B站主页~~~ Lua解释器裁剪&#xff0c;很简单~ 1、引言 在嵌入式中使用lua解释器&#xff0c;很多时候会面临资源紧张的情况。 同时&#xff0c…...

web前端设计nav:深入探索导航栏设计的艺术与技术

web前端设计nav&#xff1a;深入探索导航栏设计的艺术与技术 在web前端设计中&#xff0c;导航栏&#xff08;nav&#xff09;扮演着至关重要的角色&#xff0c;它不仅是用户浏览网站的指引&#xff0c;更是网站整体设计的点睛之笔。本文将从四个方面、五个方面、六个方面和七…...

分析解读NCCL_SHM_Disable与NCCL_P2P_Disable

在NVIDIA的NCCL&#xff08;NVIDIA Collective Communications Library&#xff09;库中&#xff0c;NCCL_SHM_Disable 和 NCCL_P2P_Disable 是两个重要的环境变量&#xff0c;它们控制着NCCL在多GPU通信中的行为和使用的通信机制。下面是对这两个环境变量的详细解读&#xff1…...

使用 Python 进行测试(6)Fake it...

总结 如果我有: # my_life_work.py def transform(param):return param * 2def check(param):return "bad" not in paramdef calculate(param):return len(param)def main(param, option):if option:param transform(param)if not check(param):raise ValueError(…...

Flink Watermark详解

Flink Watermark详解 一、概述 Flink Watermark是Apache Flink框架中为了处理乱序和延迟事件时间数据而引入的一种机制。在流处理中&#xff0c;由于数据可能不是按照事件产生的时间顺序到达的&#xff0c;Watermark被用来告知系统在该时间戳之前的数据已经全部到达&#xff…...

LeetCode538.把二叉搜索树转换为累加树

class Solution { public:int sum 0; TreeNode* convertBST(TreeNode* root) { if (root){convertBST(root->right);sum root->val;root->val sum;convertBST(root->left);}return root;}};...

关于编程思想

面向过程思想 面向过程就是分析出解决问题所需要的步骤&#xff0c;然后用函数把这些步骤一步一步实现&#xff0c;使用的时候再一个一个的依次调用就可以了 JS就是典型的面向过程的编程语言 优点&#xff1a; 性能比面向对象编程高&#xff0c;适合跟硬件联系很紧密的东西…...

521. 最长特殊序列 Ⅰ(Rust单百解法-脑筋急转弯)

题目 给你两个字符串 a 和 b&#xff0c;请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在&#xff0c;则返回 -1 。 「最长特殊序列」 定义如下&#xff1a;该序列为 某字符串独有的最长 子序列 &#xff08;即不能是其他字符串的子序列&#xff09; 。 字符串 s …...

【YashanDB知识库】PHP使用OCI接口使用数据库绑定参数功能异常

【问题分类】驱动使用 【关键字】OCI、驱动使用、PHP 【问题描述】 PHP使用OCI8连接yashan数据库&#xff0c;使用绑定参数获取数据时&#xff0c;出现报错 如果使用PDO_OCI接口连接数据库&#xff0c;未弹出异常&#xff0c;但是无法正确获取数据 【问题原因分析】 开启O…...

深入分析 Android BroadcastReceiver (三)

文章目录 深入分析 Android BroadcastReceiver (三)1. 广播消息的优缺点及使用场景1.1 优点1.2 缺点 2. 广播的使用场景及代码示例2.1. 系统广播示例&#xff1a;监听网络状态变化 2.2. 自定义广播示例&#xff1a;发送自定义广播 2.3. 有序广播示例&#xff1a;有序广播 2.4. …...

在java中使用Reactor 项目中的一个类Mono,用于表示异步单值操作

Mono 是 Reactor 项目中的一个类&#xff0c;用于表示异步单值操作。Reactor 是一个响应式编程库&#xff0c;广泛应用于 Java 中的异步编程和非阻塞 I/O 操作。Mono 可以类比为一个可能&#xff08;或将来&#xff09;包含零个或一个值的异步计算结果。与 Flux&#xff08;另一…...

LabVIEW故障预测

在LabVIEW故障预测中&#xff0c;振动信号特征提取的关键技术主要包括以下几个方面&#xff1a; 时域特征提取&#xff1a;时域特征是直接从振动信号的时间序列中提取的特征。常见的时域特征包括振动信号的均值、方差、峰值、峰-峰值、均方根、脉冲指数等。这些特征能够反映振动…...

掌握JavaScript中的`async`和`await`:循环中的使用指南

引言 在JavaScript的异步编程中&#xff0c;async和await提供了一种更接近同步代码的写法&#xff0c;使得异步逻辑更加清晰易懂。然而&#xff0c;当它们与循环结合时&#xff0c;一些常见的陷阱和误区可能会出现。本文将通过代码示例&#xff0c;指导你如何在循环中正确使用…...

java第二十三课 —— 继承

面向对象的三大特征 继承 继承可以解决代码复用&#xff0c;让我们的编程更加靠近人类思维&#xff0c;当多个类存在相同的属性&#xff08;变量&#xff09;和方法时&#xff0c;可以从这些类中抽象出父类&#xff0c;在父类中定义这些相同的属性和方法&#xff0c;所有的子…...

不可不知的Java SE技巧:如何使用for each循环遍历数组

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…...

机器人建模、运动学与动力学仿真分析(importrobot,loadrobot,smimport)

机器人建模、运动学与动力学仿真分析是机器人设计和开发过程中的关键步骤。 一、机器人建模 机器人建模是描述机器人物理结构和运动特性的过程。其中&#xff0c;URDF&#xff08;Unified Robot Description Format&#xff09;是一种常用的机器人模型描述方法。通过URDF&…...

02-QWebEngineView的使用

Qt WebEngine_hitzsf的博客-CSDN博客 一、QWebEngineView QWebEngineView 类是一个实现Web浏览器的便捷类&#xff0c;提供了back() 、forward()、reload()、stop() 等方法&#xff0c;可轻松实现页面的前进、后退、重载等导航功能&#xff0c;要实现一个简单的只有网页加载网…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...

【大厂机试题解法笔记】矩阵匹配

题目 从一个 N * M&#xff08;N ≤ M&#xff09;的矩阵中选出 N 个数&#xff0c;任意两个数字不能在同一行或同一列&#xff0c;求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求&#xff1a;1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...

Qt学习及使用_第1部分_认识Qt---Qt开发基本流程

前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...