最长单调子序列问题

Grade 0 Open Time Friday, 23 September 2011, 3:25 pm
Discount 0.8 Time Discount Friday, 23 September 2011, 3:25 pm
Allow late Yes Close Time Friday, 23 September 2011, 3:25 pm

给出一个由n个数组成的序列x[1..n],找出它的最长单调上升子序列。即求最大的m和a1,a2……,am,使得a1<a2<……<am且x[a1]<x[a2]<……<x[am]。

例:x[]={3,4,5,6,8,7,5,3,5,9};则最长的单调上升子序列长度是:6,这时m为6,a1=0,a2=1,a3=2,a4=3,a5=4或者是5都可以,a6=9,可以满足x[a1]<x[a2]<……<x[am](这时的最长单调递增子系列是3,4,5,6,8或者7,9,该子系列长度是6)

输入:

第一行为一个整数n,第二行为n个整数,表示一个长度为n的整数系列。

输出:

一个整数m,表示该整数系列的最长子系列的长度。

输入样例:

10

3 4 5 6 8 7 5 3 3 9

输出样例:

6