【晴问算法】提高篇—动态规划专题—最长上升子序列
题目描述
现有一个整数序列a1,a2,...,an,求最长的子序列(可以不连续),使得这个子序列中的元素是非递减的。输出该最大长度。
输入描述
第一行一个正整数n(1≤n≤100),表示序列长度;
第二行为用空格隔开的n个整数ai(−10^5≤ai≤10^5),表示序列元素。
输出描述
输出一个整数,表示最大长度。
样例1
输入
7
1 2 3 -1 -2 7 9
输出
5
解释
最长上升子序列为
1 2 3 7 9,长度为5。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int dp[MAXN];//dp[i]表示以a[i]元素为结尾的最大连续子序列和
int a[MAXN];//存放序列元素int main(){int n;//序列长度cin >> n;for(int i=0;i<n;i++){cin >> a[i];}dp[0] = 1;for(int i=1;i<n;i++){//对于每个位置i,要找到以a[i]结尾的最长递增子序列长度dp[i]dp[i] = 1;//初始化为1,因为至少可以构成一个长度为1的子序列for(int j=0;j<i;j++){//检查是否可以将a[i]加入到以a[j]结尾的递增子序列中if(a[i] > a[j]){//说明a[i]可以接在以a[j]结尾后dp[i] = max(dp[j] + 1,dp[i]);//dp[j]+1表示接在了以a[j]结尾的子序列长度,更新以a[i]结尾的子序列长度}}}int ans = 1;for(int i=1;i<n;i++){//不是输出最后一个dp元素,因为最后一个元素不一定在递增子序列中if(ans < dp[i]){//遍历寻找以a[i]结尾最大的子序列ans = dp[i];}}printf("%d",ans);return 0;
}
相关文章:
【晴问算法】提高篇—动态规划专题—最长上升子序列
题目描述 现有一个整数序列a1,a2,...,an,求最长的子序列(可以不连续),使得这个子序列中的元素是非递减的。输出该最大长度。 输入描述 第一行一个正整数n(1≤n≤100),表示序…...
天软特色因子看板(2024.3第5期)
该因子看板跟踪天软特色因子A08006(近一月日度买卖压力2),该因子为近一个月个股每日的相对价格位置,用以刻画股票所受买卖压力,取作 介于0~1间,指标值越大,反映股票在价格相对高位停留的时间越长,所面临的买…...
静态网络配置
一、查看网络命令 1.命令行查看网络配置 1、查看ip\硬件设备-网卡 ifconfig -a ifconfig ens160 网卡名称 ip addr show ip addr show ens160 nmcli device show ens160 nmcli con up ens160 2、主机名称 hostname hostname hfj.huaxia.com 3、查看路由和网关 rou…...
多种智能搜索算法可视化还原 3D 魔方
2024/03/19:程序更新说明(文末程序下载链接已更新) 版本:v1.0 → v1.2 ① 修复:将 CLOSED 表内容从优先级队列中分离开来,原优先级队列作 OPEN 表,并用链表树隐式地代替 CLOSED 表,以…...
Maven,pom.xml,查找 子jar包
在IDEA打开pom.xml,会看到这里: 然后如果有需要,把相关的 子jar包 去掉 <dependency><groupId>XXX</groupId><artifactId>XXX</artifactId><exclusions><exclusion><artifactId>xxx</a…...
MySQL中数据库表的监控
MySQL中数据库表的监控 (1)查看数据库中当前打开了哪些表:show OPEN TABLES ,如图6-1-5所示。另外,还可以通过show OPEN TABLES where In_use > 0过滤出当前已经被锁定的表。 查看数据库中表的状态:SHO…...
【S5PV210_视频编解码项目】裸机开发2:实现PWM波形驱动蜂鸣器
开发内容介绍 基于芯片自带的PWM定时器模块,实现对PWM波形的控制,掌握pwm定时器的驱动程序开发。 开发理论架构 1)pwm波形的产生的条件:在指定的IO口输出一定频率和占空比的波形 2)pwm波形频率的影响因素࿱…...
js进阶-深入对象-内置构造函数-包装类
一. 创建对象的三种方式 1.1 利用对象字面量创建对象 const p {name:"kebi" }1.2 利用 new Object 创建对象 // const obj new Object()// obj.uname maidi// console.log(obj)const obj new Object({ uname: maidi })1.3 利用构造函数创建对象 大写字母开头的…...
Linux作业
1.创建用户,用户名为user,user02密码均为123.com,创建完成后用tail查看用户是否存在。(截图)(10分) 2.在用户user主目录中用mkdir命令创建目录my.txt,在目录my.txt中创建文件a1.txt、1a1.txt、5…...
信息发布系统
特色功能 画布功能---可任意拖动各控件的播放位置及大小,可任意选择屏幕背景色或添加背景图 同步联屏---毫秒级同步功能 视频切换无黑屏 触摸查询系统 会议预定系统 终端显示-会议综合屏 终端显示-会议预定屏 终端显示-移动端 广告发布系统 硬件产品-智能终端 硬件…...
Dell Inspiron 戴尔灵越16plus7620升级M2硬盘
主机只支持一条M2硬盘,只能用更换更大容量硬盘的方式增加存储容量。 1、打开后盖,把新硬盘换上。旧硬盘装硬盘盒里,连上主机上。准备一个PE启动U盘, 2、开机不停地按F12,选U盘启动,进入PE,使用…...
视频怎么转mp4格式?分享3个宝藏方法,轻松学会
在当今数字化的时代,视频文件的格式多种多样,而MP4格式因其广泛的兼容性和高质量的压缩技术而备受青睐。然而,有时我们可能需要将其他格式的视频转换为MP4格式,以便在各种设备和平台上播放和分享视频。 在本文中,我们…...
Javascript 元二分搜索 | 单边二分查找(Meta Binary Search | One-Sided Binary Search)
元二分搜索(Steven Skiena 在《算法设计手册》第 134 页中也称为单边二分搜索)是二分搜索的一种修改形式,它以增量方式构建数组中目标值的索引。与普通二分搜索一样,元二分搜索需要 O(log n) 时间。 元二分搜索,也称为…...
柚见十三期(优化)
前端优化 加载匹配功能与加载骨架特效 骨架屏 : vant-skeleton index.vue中 /** * 加载数据 */ const loadData async () > { let userListData; loading.value true; //心动模式 if (isMatchMode.value){ const num 10;//推荐人数 userListData await myA…...
Node.js常用命令:了解Node.js的核心命令和用法
学习目标: 理解Node.js和npm的概念及其在开发中的作用;掌握Node.js的核心命令,包括node、npm、npx等;学会使用node命令来执行JavaScript文件和模块;熟悉npm命令,包括安装、更新、卸载依赖包等操作…...
QT 驾校系统界面布局编写
MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this);this->resize(ui->label_img->width(),ui->label_img->height());//图片自适应窗口大小ui->label_img->setScaledContents(true);//图片置…...
【Auth Proxy】为你的 Web 服务上把锁
Auth Proxy 一个极简的用于 Web 服务鉴权的反向代理服务 极其简约的 UI对你的真实服务无任何侵入性支持容器部署,Docker Image 优化到不能再小(不到 9MB)GitHub:https://github.com/wengchaoxi/auth-proxy 效果 我在 http://lo…...
Docker 从0安装 nacos集群
前提条件 Docker支持一下的CentOs版本 Centos7(64-bit),系统内核版本为 3.10 以上Centos6.5(64-bit) 或者更高版本,系统内核版本为 2.6.32-431 或者更高版本 安装步骤 使用 yum 安装(CentOS 7下) 通过 uname -r 命令查看你当…...
keithley2612A数字源表
181/2461/8938产品概述: Keithley 2612A源表既可用作台式I-V表征工具,也可用作多通道I-V测试系统的构建模块组件。对于台式使用,吉时利2612ASourceMeter具有嵌入式TSP Express软件工具,允许用户快速轻松地执行常见的I-V测试&…...
AI助手 - 月之暗面 Kimi.ai
前言 这是 AI工具专栏 下的第四篇,这一篇所介绍的AI,也许是截至今天(204-03-19)国内可访问的实用性最强的一款。 今年年初,一直看到有人推荐 Kimi,不过面对雨后春笋般的各类品质的AI,说实话也有…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
