最长不下降子序列（要把所求序列输出来）

一个数的序列bi，当b1 <= b2 <= ... < =bS的时候，我们称这个序列是不下降的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些不下降的子序列(ai1, ai2, ..., aiK)，这里1<= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些不下降子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

Input

多组cas ， 每组cas 两行：

第一行 输入一个数 n (n < 10000)， 表示有n个数

第二行 n个数， 分别代表每个数；

Output

每个cas 一行  输出 该书数列的最长的长度 ；

Sample Input

7

1 7 3 5 9 4 8

Sample Output

输出最长的序列

#include<iostream>  
using namespace std;  
#define MAX 10001  
void vInput(int nArr[],int nN);  
int nGetResult(int nArr[],int nN);  
void vOut(int nOut); 
int nFind(int nUp[],int nV,int high,int low); 
int main()  
{  
    int nNum;  
    int nData[MAX];  
    int nAns;  
    while(1==scanf("%d",&nNum))  
    {  
        vInput(nData,nNum);  
        nAns=nGetResult(nData,nNum);  
        vOut(nAns);  
    }  
    return 0;  
}  
void vInput(int nArr[],int nN)  
{  
    int i;  
    for(i=1;i<=nN;i++)  
    {  
        scanf("%d",&nArr[i]);  
    }  
}  
int nGetResult(int nArr[],int nN)  
{  
    int i;  
    int upLimit[MAX];  
    int nCount;  
    int nPos;   
    for(i=1;i<=nN;i++)  
    { 
        upLimit[i]=nArr[nN]; 
    } 
    nCount=1; 
    for(i=nN-1;i>=1;i--) 
    {  
        if(nArr[i]<=upLimit[nCount]) 
        { 
            nCount++; 
            upLimit[nCount]=nArr[i]; 
        } 
        else 
        { 
            if(nArr[i]>upLimit[1]) 
            { 
                upLimit[1]=nArr[i]; 
            } 
            else 
            { 
                nPos=nFind(upLimit,nArr[i],nCount,1); 
                upLimit[nPos]=nArr[i]; 
            } 
        } 
    } 
    return nCount;  
} 
int nFind(int nUp[],int nV,int high,int low) 
{ 
    int nRet; 
    int nMid; 
    if(high==low) 
    { 
        nRet=high; 
        return nRet; 
    } 
    nMid=(high+low)/2; 
    if(nV>nUp[nMid]) 
    { 
        nRet=nFind(nUp,nV,nMid,low); 
    } 
    else 
    { 
        nRet=nFind(nUp,nV,high,nMid+1); 
    } 
    return nRet; 
}
void vOut(int nOut)  
{  
    printf("%d\n",nOut);  
}