网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
最长单调子序列问题
成绩 | 0 | 开启时间 | 2011年09月23日 星期五 15:25 |
折扣 | 0.8 | 折扣时间 | 2011年09月23日 星期五 15:25 |
允许迟交 | 是 | 关闭时间 | 2011年09月23日 星期五 15: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