当前位置:首页 > 题解目录 > 正文内容

【题解】最长上升子序列

亿万年的星光2年前 (2023-05-13)题解目录1431

【题目描述】

一个数的序列bi,当b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...,aiK),这里1≤i1<i2<...<iK≤N。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8)。

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

【输入描述】

输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

【输出描述

最长上升子序列的长度。

【样例输入】

7
1 7 3 5 9 4 8

【样例输出】

4


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】高精度除法

【题目描述】高精除以高精,求它们的商和余数。【输入描述】输入两个低于300位的正整数。【输出描述】输出商和余数。【样例输入】12313123184575776878979876423245678643...

【题解】小X与机器人

【题解】小X与机器人

【题目描述】小X的老师很喜欢围棋。众所周知,围棋的棋盘有19行19列,共有361个交叉点。为方便起见,我们把这些行列按顺序编号为1~19,并用(x, y)表示第x列第y行的位置。例如下图中,A用(16...

【题解】营救巨轮

【题目描述】一艘远洋巨轮在大海中遇到故障,船长库克立刻发出了求救信号。距离最近的辽宁号收到了讯息,时间就是生命,必须尽快赶到那里。通过侦测,辽宁号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小...

【题解】2002-T2 选数

【题解】2002-T2 选数

【题目描述】已知n个整数x1,x2,……xn,以及一个整数K(K<n)。从n个整数中任选k个整数相加,可分别 得到一系列的和。例如当n=4, =3, 4个整数分别为3,7,12,1...

【题解】分糖果

【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

【题解】阶乘的末尾

【题目描述】n的阶乘定义为n!=1*2*3*……*n  如3!=6   n!通常最后会有很多0,如5!=120  最后有一个0,现在统计n!去除末尾的0后,最后k位是多少...