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.

输入格式

There are several test cases (less than 100 test cases).

Every test case includes two lines. 

The first line 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 must contain a single integer for every test case. It's the length of the longest
  ordered subsequence of the given sequence.

输入样例

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

输出样例

4
4
5

提示

一，对输入字符串的处理

注意：这道题和其他题的输入输出不同,这题是接收多组数据而非单组,以0来判别结束。
大家在接受数据的时候，不要用(c=getchar())!='
'诸如此类一个字符一个字符接受，
然后判断是否是回车符号来结束一行的输入，这样的方式在你本机运行不会有问题，
但OJ系统中会有错误，无法输出结果，因为测试平台行末并非'
'字符。
这里接受数据用scanf的%d或%s，或cin等，会自动判别结束字符的，你就不要在你程序
里专门去判别或吸收回车字符。

对于最后一组数据输入为0表示结束，只要判断接受的第一个字符是否为0且字符串长度
为1就结束，无须去处理回车字符。

输入的序列可以用整型数组或字符串数组保存。


二，算法的动态规划思想

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

设f(i)表示：从左向右扫描过来直到以a[i]元素结尾的序列，可获得的最长上升
子序列的长度，且最长上升子序列包含a[i]元素（1<=i<=n）。

（这里大家思考一下，为何要这样假设子问题和子问题最优解f(i)？
有同学问：为何最长上升子序列要包含a[i]元素（1<=i<=n）？
因为你所设的子问题要和更下一级子问题关联起来。如果长度为i序列的最长上升
子序列中没有规定包含a[i]元素，那如何和其前缀的最长上升子序列问题关联起来
呢？因为你没法确认你前缀的最长上升子序列最后一个字符在哪里？上升子序列的
边界在哪不知道的话，很难和更小规模的子问题联系起来，显然是比较麻烦的。）

f(i)是从f(1),f(2), ……到f(i-1)中找最大的一个值，再加1，或者就是1。
这主要得看a[i]这个元素能否加入到之前已经获得的最长上升子序列当中去，
如果能加入，是之前已获得的最长上升子序列长度加1；
如果不能加入，就开始一个新的上升子序列，长度为1。
最后，所要求的整个序列的最长上升子序列长度为 max{ f(i): 1<=i<=n }

f(i)的递推公式如下：
（1）f(i) = 1              当i=1;
（2）f(i) = max{f(j)+1}    当i>1, 对某个前面的j(1<=j<i), 有a[j]<a[i]];
（3）f(i) = 1              当i>1, 对任意j(1<=j<i), 都有a[j]>=a[i]

例子，对于序列：4  2  6  3  1  5  2
   i = 1  2  3  4  5  6  7
a[i] = 4  2  6  3  1  5  2
f(i) = 1  1  2  2  1  3  2

这里max{f(i)}=3为原问题所求的最长上升子序列的长度。

效率分析：
f(i)的计算不超过O(n)，因此，整个算法为O(n^2)。

我的代码实现：

 1 #include<stdio.h>
 2 #define N 1001
 3 
 4 int a[N],f[N];
 5 
 6 
 7 int min(int n){
 8     int min1=f[1];
 9     for(int i=2;i<=n;i++){
10         if(min1>f[i])min1=f[i];
11     }
12     return min1;
13 }
14 
15 int max(int n){
16     int max1=f[1];
17     for(int i=2;i<=n;i++){
18         if(max1<f[i])max1=f[i];
19     }
20     return max1;
21 }
22 
23 
24 
25 
26 void Longest(int n){
27     f[1]=1;
28     for(int i=2;i<=n;i++){
29         if(a[i]<min(i-1))f[i]=1;
30         else {
31             for(int j=1;j<i;j++){
32                 if(a[j]>a[i])continue;
33                 else {
34 //                    if((f[i]<(max(j)+1)))f[i]=max(j)+1;  //此处max(j)当中的j已经更新到最后一个，会把前面的a[j]>a[i]的带进来，所以是不对的  
35                     if(f[i]<(f[j]+1))f[i]=f[j]+1;
36                 }
37             }
38         }
39     }
40 }
41 
42 
43 int main(){
44     int n;
45     while(scanf("%d",&n)){
46         if(n==0)break;
47     for(int i=1;i<=n;i++){
48         scanf("%d",&a[i]);
49     }
50     for(int i=1;i<=n;i++){
51         f[i]=0;
52     }
53     Longest(n);
54     printf("%d
",max(n));
55     }
56     return 0;
57 }