(AcWing) 最长上升子序列

news/2024/2/28 16:19:54

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

输入格式

第一行包含整数 N。

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

输出格式

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

数据范围

1≤N≤1000,
−109≤数列中的数≤109

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

线性DP: 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N = 1010,INF = 1e9+10;int a[N];
int 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 res = 0;for(int i=1;i<=n;i++) res = max(res,f[i]);cout<<res<<endl;return 0;
}

 


http://www.ppmy.cn/news/1055010.html

相关文章

算法01 跟左神刷题01

题目一 给定一个有序数组arr&#xff0c;代表坐落在X轴上的点&#xff0c;给定一个正数K&#xff0c;代表绳子的长度 返回绳子最多压中几个点?即使绳子边缘处盖住点也算盖住。 题的理解 贪心也行&#xff0c; 然后比如绳子的最右端到了973 绳子长度为100 而这是个有序数组…

java实现字符串匹配英文字母和数字开头的内容

只想匹配英文字母和数字开头的内容&#xff0c;可以使用以下的正则表达式&#xff1a;[a-zA-Z0-9] 以下是一个示例代码&#xff1a; import java.util.regex.Matcher; import java.util.regex.Pattern;public class Main {public static void main(String[] args) {String ss…

vue2,使用element中的Upload 上传文件,自定义上传http-request上传,上传附件支持多选,多个文件只发送一次请求,代码里有注释

复制直接使用&#xff0c;组件根据multiple是否多选来返回附件内容&#xff0c;支持多选就返回数据附件&#xff0c;则返回一个附件对象。 //uploadFiles.vue<template><div><el-uploadclass"avatar-uploader"action"#":accept"accep…

【网络】DNS | ICMP | NAT | 代理服务器

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《网络》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 前面几篇文章虽然讲介绍了整个网络通信的协议栈&#xff0c;我们也知道了完整的网络通信过程&#xff…

js数组操作的shift unshift pop push用法

Array.shift() shift() 方法用在数组上&#xff0c; 移除数组的第一个元素并返回移除的元素. 该方法会改变原数组的长度. const array1 [1, 2, 3];const firstElement array1.shift();console.log(array1); // Expected output: Array [2, 3]console.log(firstElement); …

【校招VIP】有一个比赛获奖项目和参与的开源小项目,秋招项目竞争力够不够?三个标准,自己都可以估算

有个24届的学生问我&#xff1a;现在没有实习&#xff0c;能不能参与大厂秋招&#xff1f;手里有两个项目&#xff0c;一个是比赛的获奖项目&#xff0c;一个是CSDN上博主做的开源小项目&#xff0c;这两个项目竞争力够不够&#xff1f; 其实项目这块&#xff0c;无非就是三个…

删除链表的中间节点

题目&#xff1a; 示例&#xff1a; 思路&#xff1a; 这个题类似于寻找链表中间的数字&#xff0c;slow和fast都指向head&#xff0c;slow走一步&#xff0c;fast走两步&#xff0c;也许你会有疑问&#xff0c;节点数的奇偶不考虑吗&#xff1f;while执行条件写成fast&&…

把握医学营养趋势 健启星加速突围

随着“健康中国”战略的提出&#xff0c;大健康产业上升到国家战略高度&#xff0c;进入高速发展期。市场数据显示&#xff0c;医学营养市场发展势头迅猛&#xff0c;年平均增速超过30%&#xff0c;中国医学营养市场也迎来高速发展。但目前品牌处于高度分散的状态&#xff0c;市…

【leetcode】第五章 栈与队列part03

239. 滑动窗口最大值 队列的应用&#xff1a;单调队列 当滑动窗口向右移动时&#xff0c;我们需要把一个新的元素放入队列中。为了保持队列的性质&#xff0c;我们会不断地将新的元素与队尾的元素相比较&#xff0c;如果前者大于等于后者&#xff0c;那么队尾的元素就可以被永…

postman接口自动化测试框架实战!

什么是自动化测试 把人对软件的测试行为转化为由机器执行测试行为的一种实践。 例如GUI自动化测试&#xff0c;模拟人去操作软件界面&#xff0c;把人从简单重复的劳动中解放出来。 本质是用代码去测试另一段代码&#xff0c;属于一种软件开发工作&#xff0c;已经开发完成的用…

An easy problem

一、题目 we define f(A) 1, f(a) -1, f(B) 2, f(b) -2, … f(Z) 26, f(z) -26; Give you a letter x and a number y , you should output the result of yf(x). Input On the first line, contains a number T.then T lines follow, each line is a case.each case …

多线程基础篇(包教包会)

文章目录 一、第一个多线程程序1.Jconsole观察线程2.线程休眠-sleep 二、创建线程三、Thread类及常见方法1. Thread 的常见构造方法2. Thread 的几个常见属性3. 启动线程 - start4. 中断线程5. 等待一个线程 四、线程状态五、线程安全问题(synchronized)&#xff08;重点&#…

使用Python内置模块加速SQL查询

大家好&#xff0c;假设你正在查阅一本书的页面&#xff0c;你想要更快地找到你正在寻找的信息。那么你可能会查找术语索引&#xff0c;然后跳转到引用特定术语的页面&#xff0c;SQL中的索引与书籍中的索引工作原理类似。 在大多数实际系统中&#xff0c;都将对包含大量行的数…

C++信息学奥赛1130:找第一个只出现一次的字符

这段代码的功能是找出输入字符串中第一个重复出现的字符&#xff0c;并输出该字符。 解析注释后的代码如下&#xff1a; #include<bits/stdc.h> using namespace std; int main() {string arr;getline(cin, arr); int a0;for(int i0;i<arr.length();i){for(int j0;j…

英伟达™(NVIDIA®)535.98 Linux 图形驱动程序发布

导读英伟达™&#xff08;NVIDIA&#xff09;公司近日发布了适用于 Linux、FreeBSD 和 Solaris 系统的 NVIDIA 535.98 图形驱动程序&#xff0c;作为其生产分支的维护更新&#xff0c;解决了各种错误和问题。 在英伟达™&#xff08;NVIDIA&#xff09;535.86.05 版本发布仅三周…

如何深入理解 JavaScript 中的懒加载

懒加载是一种延迟加载非必要内容的方法&#xff0c;直到用户需要查看它为止。与其他加载方法不同&#xff0c;其他加载方法在访问页面时同时加载所有网站资源&#xff0c;而懒加载采取更加谨慎的方式。它延迟显示某些元素&#xff0c;如图片、视频和其他多媒体&#xff0c;直到…

每日汇评:英镑的韧性掩盖了更广泛的疲态,英镑相关货币分析

1、尽管英国CPI数据强劲&#xff0c;但英镑/美元未能延续涨势&#xff1b; 2、欧元/英镑向下突破的时机可能已经成熟&#xff0c;英镑/日元的反弹目前正在失去动力&#xff1b; 3、英镑交叉盘的关键水平至关重要&#xff1b; 上周英国公布强劲通胀数据后&#xff0c;英镑未能…

使用 ChatGPT 创建 PowerPoint 演示文稿

让 ChatGPT 成为您的助手来帮助您编写电子邮件很简单,因为众所周知,它非常能够生成文本。很明显,ChatGPT 无法帮助您做饭。但您可能想知道它是否可以生成文本以外的其他内容。在上一篇文章中,您了解到 ChatGPT 只能通过中间语言为您生成图形。在这篇文章中,您将了解使用中…

【洁洁送书第五期】为什么我们要了解可观测性工程

导读 可观测性已成为一个热门话题&#xff0c;并广受关注。随着它的普及&#xff0c;“可观测性”不幸被误作“监控”或“系统遥测”的同义词。可观测性是软件系统的一个特征。而且&#xff0c;只有当团队采用新的实践进行持续开发时&#xff0c;才能在生产软件系统中有效利用这…

CSS 实现页面底部加载中与加载完毕效果

效果图 实现代码 <view class"bottom-load-tip"><view class"line-tip"></view><view class"loading-animation" v-if"!lastPage"></view><view>{{ lastPage ? "没有更多了" : "…
最新文章