问题b.txt

来自「Problem B:Longest Ordered Subsequence A」· 文本 代码 · 共 49 行

Problem B:Longest Ordered Subsequence

Time Limit:2000MS  Memory Limit:65536K
Total Submit:2 Accepted:2 

Language: not limited


Description 

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). 

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence. 


Input 

There are several test cases. Every test case includes two lines. 
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000 
When N is 0, it indicates test to end. 


Output 

Output file must contain a single integer for every test case ---- the length of the longest ordered subsequence of the given sequence. 


Sample Input 


7
1 7 3 5 9 4 8
6
1 8 3 6 5 9
5
1 2 3 4 5
0

Sample Output 


4
4
5

Hint 

考虑采用动态规划算法，针对每个元素，以该元素结尾的最长有序子序列作为子问题，计算出每个子问题的最大长度用“表”记录下来。先写出递推关系式再编程实现。