Problem D: 最长上升子序列

Problem D: 最长上升子序列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 56  Solved: 7
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个n长数组,后跟n个数,求该序列中的最长上升子序列

Input

单组输入:
第一行输入一个n(n<=3000);
第二行输入n个数:a[1],a[2]........a[n]
a[i]>0&&a[i]<10^30;(不包含前导0;例:001)

Output

输入包含一行,即n长数组的最长上升子序列的长度(严格单调递增,例:1,2,3·······)

Sample Input Copy

5
1 2 3 4 5

5
1 2 5 3 4

Sample Output Copy

5

4