题目描述
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,如果序列Y=“y0,y1,…,yk-1”是X的子序列,就要满足存在X的一个严格递增下标序列i0,i1,…,ik-1,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
最长上升子序列,指一个序列中最长的单调递增的子序列。
给定N个数,求这N个数的最长上升子序列的长度。
输入描述
第一行输入一个整数N( 1<=N<=1000 )。
第二行输入N个整数,每个整数不超过10000。
输出描述
输出一行,包含一个整数,表示最长上升子序列的长度。
样例输入
7
2 5 3 4 1 7 6
样例输出
4
提示
中,2 3 4 7和2 3 4 6就是序列2 5 3 4 1 7 6的两种选取方案,最长的长度是4。