最长不降子序列

最长不降子序列
（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<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；
2· 若从a(n-1)开始查找，则存在下面的两种可能性：
①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:
在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。

4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号
(3) 程序如下:（逆推法）

program li1;
const maxn=100;
var a,b,c:array[1..maxn] of integer;
    fname:string;
    f:text;
    n,i,j,max,p:integer;
begin
readln(fname);
assign(f,fname);
reset(f);
readln(f,n);+
for i:=1 to n do
  begin
  read(f,a);
  b[n]:=1;
  c[n]:=0;
  end;
for i:= n-1 downto 1 do
  begin
   max:=0;p:=0;
   for j:=i+1 to n do
    if (a<a[j]) and (b[j]>max) then  beginmax:=b[j];p:=j end;
   if p<>0 then begin b:=b[p]+1;c:=p end
  end;
max:=0;p:=0;
for i:=1 to n do
  if b>max then begin max:=b;p:=i end;
writeln('maxlong=',max);
write('result is:');
while p<>0 do
  begin write(a[p]:5);p:=c[p] end;
end.