B3637 最长上升子序列

news/2024/6/17 6:38:17

# 最长上升子序列

## 题目描述

这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的**最长上升子序列**的长度。

最长上升子序列是指,从原序列中**按顺序**取出一些数字排在一起,这些数字是**逐渐增大**的。

## 输入格式

第一行,一个整数 $n$,表示序列长度。

第二行有 $n$ 个整数,表示这个序列。

## 输出格式

一个整数表示答案。

## 样例 #1

### 样例输入 #1

```
6
1 2 4 1 3 4
```

### 样例输出 #1

```
4
```

## 提示

分别取出 $1$、$2$、$3$、$4$ 即可。

代码实现

#include<iostream>
using namespace std;
const int N=5010;
int a[N],f[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;  //只有a[i]一个数for(int j=1;j<i;j++){if(a[j]<a[i])f[i]=max(f[i],f[j]+1);} }int ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[i]);cout<<ans<<endl;return 0;
}


http://www.mrgr.cn/p/54680307

相关文章

【Chat GPT】用 ChatGPT 运行 Python

前言 ChatGPT 是一个基于 GPT-2 模型的人工智能聊天机器人&#xff0c;它可以进行智能对话&#xff0c;同时还支持 Python 编程语言的运行&#xff0c;可以通过 API 接口进行调用。本文将介绍如何使用 ChatGPT 运行 Python 代码&#xff0c;并提供一个实际代码案例。 ChatGPT …

golang pprof

pprof是一个用于分析数据的可视化和分析工具&#xff0c;由谷歌公司的开发团队使用go语言编写成的。一般用于对golang资源占用进行分析。不是原创&#xff0c;参考&#xff1a;https://juejin.cn/post/7122473470424219656 1. 通过页面查看golang运行情况 访问 http://127.0.0…

PostgreSql 锁

一、概述 在 PostgreSQL 事务中提到&#xff0c;多个用户访问相同数据时可能出现脏读&#xff0c;不可重复度&#xff0c;幻读&#xff0c;更新丢失的问题&#xff0c;为解决这些问题&#xff0c;定义了不同的隔离级别&#xff0c;而隔离级别的具体实现&#xff0c;依靠的就是数…

Kubernetes 使用 helm 部署 NFS Provisioner

文章目录 1. 介绍2. 预备条件3. 部署 nfs4. 部署 NFS subdir external provisioner4.1 集群配置 containerd 代理4.2 配置代理堡垒机通过 kubeconfig 部署 部署 MinIO添加仓库修改可配置项 访问nodepotingress 1. 介绍 NFS subdir external provisioner 使用现有且已配置的NFS…

在外远程NAS群晖Drive - 群晖Drive挂载电脑磁盘同步备份【无需公网IP】

文章目录 前言1.群晖Synology Drive套件的安装1.1 安装Synology Drive套件1.2 设置Synology Drive套件1.3 局域网内电脑测试和使用 2.使用cpolar远程访问内网Synology Drive2.1 Cpolar云端设置2.2 Cpolar本地设置2.3 测试和使用 3. 结语 前言 群晖作为专业的数据存储中心&…

tinkerCAD案例:24. Ruler - Measuring Lengths 标尺 -量勺

tinkerCAD案例&#xff1a;24. Ruler - Measuring Lengths 标尺 - 测量长度 Project Overview: 项目概况&#xff1a; A machine shop, where any idea can become a reality, can cost millions and million of dollars. Still, the most important tool in the shop is the…

“华为杯”研究生数学建模竞赛2019年-【华为杯】D题:汽车行驶工况构建

目录 摘 要&#xff1a; 1.问题背景与问题重述 1.1 问题背景 1.2 问题重述 2.模型假设 3.符号说明 4.问题一的求解 4.1 问题分析 4.2 异常数据的处理 4.2.1 明显错误数据的处理 4.2.2 加减速异常数据的处理 4.3 缺失数据的处理 4.3.1 数据插补处理 4.3.2 视为长期停车处理 4.3.…

Linux 学习记录60(ARM篇)

Linux 学习记录60(ARM篇) 本文目录 Linux 学习记录60(ARM篇)一、SPI总线1. 概念2. 硬件连接 二、SPI总线协议三、SPI总线通信模式四、对比IIC总线和SPI总线1. 相同点2. 不同点 思维导图 一、SPI总线 1. 概念 1、SPI总结是Motorola首先提出的全双工三线/四线同步串行总线 2、采…

车道线检测|利用边缘检测的原理对车道线图片进行识别

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 这两个都是博主在学习Linux操作系统过程中的记录&#xff0c;希望对大家的学习有帮助&#xff01; 操作系统Operating Syshttps://blog.csdn.net/yu_cblog/category_12165502.html?spm1001.2014.3001.5482Linux S…

15.Netty源码之EventLoop

highlight: arduino-light Netty配置主从Reactor模式 通过将NioServerSocketChannel绑定到了bossGroup。 将NioServerSocketChannel接收到请求创建的SocketChannel放入workerGroup。 将2个不同的SocketChannel绑定到2个不同的Group完成了主从 Reactor 模式。 分配NIOEventLoop的…

Git的安装以及本地仓库的创建和配置

文章目录 1.Git简介2.安装Git2.1在Centos上安装git2.2 在ubuntu上安装git 3.创建本地仓库4.配置本地仓库 1.Git简介 Git是一个分布式版本控制系统&#xff0c;用于跟踪和管理文件的更改。它可以记录和存储代码的所有历史版本&#xff0c;并可以方便地进行分支管理、合并代码和协…