最长不下降子序列长度
对于序列(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);
}