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

最长不下降子序列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 100001void 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);}