最长单调子序列问题

成绩 0 开启时间 2011年09月23日 星期五 10:25
折扣 0.8 折扣时间 2011年09月23日 星期五 10:25
允许迟交 关闭时间 2011年09月23日 星期五 10:25

给出一个由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