最长不上降子序列长度

最长不下降子序列长度
对于序列(1, 7, 3, 5, 9, 4,，有它的一些不下降子序列
如(1, 7), (3, 4,等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5,。
Input

多组cas ， 每组cas 两行：

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

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

Output

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


Sample Input

7

1 7 3 5 9 4 8

Sample Output

4





#include<iostream>

using namespace std;

#define MAX 10001

void vInput(int nN,int nA[]);
int nGetLong(int nN,int nA[]);
int nFind(int nUL[],int nA,int nHigh,int Low);
void vOut(int nOut);

int main()
{
    int nNum;
    int nArr[MAX];
    int nAns;

    while(1==scanf("%d",&nNum))
    {
        vInput(nNum,nArr);
        nAns=nGetLong(nNum,nArr);
        vOut(nAns);
    }
    return 0;
}


void vInput(int nN,int nA[])
{
    int i;

    for(i=1;i<=nN;i++)
    {
        scanf("%d",&nA[i]);
    }
}

int nGetLong(int nN,int nA[])
{
    int i;
    int nCount;
    int nUpLimit[MAX];
    int nPos;

    for(i=1;i<=nN;i++)
    {
        nUpLimit[i]=nA[nN];
    }

    nCount=1;
    for(i=nN-1;i>=1;i--)
    {
        if(nA[i]<=nUpLimit[nCount])
        {
            nCount++;
            nUpLimit[nCount]=nA[i];
        }
        else
        {
            nPos=nFind(nUpLimit,nA[i],nCount,1);
            nUpLimit[nPos]=nA[i];
        }
    }
    return nCount;
}

int nFind(int nUL[],int nA,int nHigh,int nLow)
{
    int nMid;
    int nRet;

    nMid=(nHigh+nLow)/2;
    if(nHigh==nLow)
    {
        nRet=nHigh;
        return nRet;
    }
    if(nA>nUL[nMid])
    {
        nRet=nFind(nUL,nA,nMid,nLow);
    }
    else
        nRet=nFind(nUL,nA,nHigh,nMid+1);
    
    return nRet;
}

void vOut(int nOut)
{
    printf("%d\n",nOut);
}