最长上升子序列

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 lis1.in 输出文件 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。