最长上升子序列

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file lis1.in Output file lis1.out

【题目描述】


设有整数序列A[1],A[2],A[3],…,A[m],若存在下标i1<i2<i3<…<in,且A[i1]<A[i2]<A[i3]<…<A[in],则称 序列A[1],A[2],A[3],…,A[m]中有长度为n的上升子序列A[i1] , A[i2] ,A[i3] ,…,A[in]。

请编程计算指定序列的最长上升子序列长度。


【输入格式】

第一行一个正整数n(n<1001),表示序列中整数个数;

第二行是空格隔开的n个整数组成的序列。

【输出格式】

一个正整数,表示输入文件中整数序列的最长上升子序列的长度。

【样例输入】

  7

1 7 3 5 9 4 8

【样例输出】

4

【样例说明】

 序列(1,7,3,5,9,4,8)最长上升序列有:(1,3,5,9),(1,3,5,8),(1,3,4,9),他们长度为4。