最长不下降子序列O(nlogn) --动态规划

题目：

设有一个正整数的序列：d1,d2,…，dn，对于下标i1<i2<…＜im，若有di1≤di2≤…≤dim 

则称存在一个长度为m的不下降序列。 

  例如，下列数列 

     13  7  9  16  38  24  37  18  44  19  21  22  63  15 

  对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存在长度为5的不下降序列。 

#include<stdio.h>

#define MAX 100001

void vInput(int nDa[],int nN);
int nGetSum(int nDa[],int nN);
int nFind(int nArr[],int nV,int nCHight,int nCLow);
void vOutput(int nRet);

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

	while(1 == scanf("%d",&nNum))
	{
		vInput(nData,nNum);
		nAns = nGetSum(nData,nNum);
		vOutput(nAns);
	}

	return 0;
}

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

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

int nGetSum(int nDa[],int nN)
{
	int i;
	int nPos;
	int nCount;
	int nUpLimit[MAX];

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

	return nCount;
}

//二分查找
int nFind(int nArr[],int nV,int nCHight,int nCLow)
{
	int nCMid;
	int nAns;

	if(nCHight == nCLow)
	{
		nAns = nCHight;
		return nAns;
	}
	nCMid = (nCHight+nCLow)/2;
	if(nV > nArr[nCMid])
	{
		nAns = nFind(nArr,nV,nCMid,nCLow);
	}
	else
	{
		nAns = nFind(nArr,nV,nCHight,nCMid+1);
	}

	return nAns;
}

void vOutput(int nRet)
{
	printf("%d\n",nRet);
}