A7934.最长上升子序列

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

输入格式

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

输出格式

最长上升子序列的长度

输入输出样例

  • 输入#1

    7
    1 7 3 5 9 4 8

    输出#1

    4

【普及组算法10】动态规划

0/18
首页