当前位置: 首页 > 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;要实现一个简单的只有网页加载网…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...