最长上升子序列-动态规划

?设有一个正整数的序列：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 10000void vInput(int nDa[],int nN);int nGetSum(int nDa[],int nN);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,j;int nTemp;int nCount[MAX];int nOut = 1;//初始化一维数组,存放最后一位值到当前值最长上升子序列的个数for(i=1;i<=nN;i++){nCount[i] = 0;}//以自底向上的方法，从后往前for(i=nN;i>=1;i--){nTemp = 0;//当前值往后遍历，找到上升子序列的个数最大的for(j=i+1;j<=nN;j++){if(nDa[i] < nDa[j]){if(nTemp < nCount[j])nTemp = nCount[j];}}nCount[i] = nTemp+1;if(nOut <= nTemp)nOut = nTemp+1;}return nOut;}void vOutput(int nRet){printf("%d\n",nRet);}/*71 5 9 6 5 8 9*/