最长不下降序列
设有由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的不下降序列。
下面是求一个最长不下降序列的pascal代码
program max_rise(input,output);
const maxn=100;fname='q21.txt';
type tlist=array[1..maxn,1..3] of integer;
var d:tlist;n:byte;
procedure init;
var
i:integer;
f:text;
begin
assign(f,fname);
reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,d[i,1]);
d[i,2]:=1;
d[i,3]:=0
end;
close(f);
end;
procedure make;
var
i,j,p:byte;
l:integer;
begin
for i:=n-1 downto 1 do
begin
l:=0;p:=0;
for j:=i+1 to n do
if (d[i,1]<d[j,1]) and (d[j,2]>l) then
begin
l:=d[j,2];
p:=j;
end;
if l>0 then
begin
d[i,2]:=l+1;
d[i,3]:=p;
end;
end;
end;
procedure output;
var
i,l,dmax:byte;
begin
write('source:');
for i:=1 to n do write(d[i,1]:5);
writeln;
dmax:=d[1,2];
l:=1;
for i:=2 to n-1 do
if d[i,2]>dmax then
begin
dmax:=d[i,2];
l:=i;
end;
write('result is: ');
while l<>0 do
begin
write(d[l,1]:5);
l:=d[l,3];
end;
writeln;
writeln('max length=',d[dmax,2]);
end;
begin
init;
make;
output;
end.
input:
10
3 18 7 14 10 12 23 41 16 24
output:
source: 3 18 7 14 10 12 23 41 16 24
result is: 3 7 10 12 23 41
max length = 6