最长不下降子序列

《最长不下降子序列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求最长不下降序列一．问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j)(i<>j)例如3，18，7，14，10，12，23，41，16，24。若存在i1

2、(n)开始查找时，只存在长度为1的不下降序列；2·若从a(n-1)开始查找，则存在下面的两种可能性：①若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3·一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。倒推公式为F（I）=MAX{F（I+K）}+1F[I]：表示以第I个位置为起点的最长不下降序列的长度。K的选择范围：a(I+k)>a(i)I+k≦n最后从F

3、[1]到F[N]中选取最大的即为最优解当然也可以采用顺推的方法，顺推公式为F（I）=MAX{F（I-K）}+1F[I]：表示以第I个位置为终点的最长不下降序列的长度。K的选择范围：a(I-k)

4、面给出求最长不下降序列的算法:FORI=N-1TO1STEP-1L=0:P=0FORJ=I+1TONIFD(I,1)LTHENL=D(J,2)P=JENDIFNEXTJIFL>0THEND(I,2)=L+1D(I,3)=PENDIFNEXTI下面找出最长不下降序列：DMAX=D(1,2)L=1FORI=2TON-1IFD(I,2)>DMAXTHENDMAX=D(I,2)L=I{记录最长不下降序列的起点位置}ENDIFNEXTI最长不下降序列长度为D(L,2)序列WHILEL<>0PRINTD(L,1);L=D(L,3)WEND（3）程

5、序清单PROGRAMMAX_RISE(INPUT,OUTPUT);CONSTMAXN=100;FNAME='Q21.TXT';TYPETLIST=ARRAY[1..MAXN,1..3]OFINTEGER;VARD:TLIST;N:BYTE;PROCEDUREINIT;VARI:INTEGER;F:TEXT;BEGINASSIGN(F,FNAME);RESET(F);READLN(F,N);FORI:=1TONDOBEGINREAD(F,D[I,1]);D[I,2]:=1;D[I,3]:=0END;CLOSE(F);END;PROCEDUREMAKE;VARI,J,P:

6、BYTE;L:INTEGER;BEGINFORI:=N-1DOWNTO1DOBEGINL:=0;P:=0;FORJ:=I+1TONDOIF(D[I,1]L)THENBEGINL:=D[J,2];P:=J;END;IFL>0THENBEGIND[I,2]:=L+1;D[I,3]:=P;END;END;END;PROCEDUREOUTPUT;VARI,L,DMAX:BYTE;BEGINWRITE('SOURCE:');FORI:=1TONDOWRITE(D[I,1]:5);WRITELN;DMAX:=D[1,2];L:=1;FORI:

7、=2TON-1DOIFD[I,2]>DMAXTHENBEGINDMAX:=D[I,2];L:=I;END;WRITE('RESULTIS:');WHILEL<>0DOBEGINWRITE(D[L,1]:5);L:=D[L,3];END;WRITELN;WRITELN('MAXLENGTH=',D[DMAX,2]);END;BEGININIT;MAKE;OUTPUT;END.INPUT:10318714101223411624OUTPUT:SOURCE:318714101223411624RESULTIS:3710122341MAXLENGTH=6