LNACS - VOI10 - Dãy con chung không liền kề dài nhất
Tác giả: skyvn97
Ngôn ngữ: Pascal
program LNACS;
const MAXN=1111;
var
m,n:integer;
a,b:array [-1..MAXN] of integer;
f,g:array [-1..MAXN,-1..MAXN] of integer;
function max(x,y,z:integer):integer;
begin
if (x>=y) and (x>=z) then exit(x);
if (y>=x) and (y>=z) then exit(y);
if (z>=x) and (z>=y) then exit(z);
end;
procedure init;
var
i:integer;
begin
read(m,n);
for i:=1 to m do read(a[i]);
for i:=1 to n do read(b[i]);
end;
procedure optimize;
var
i,j,res:integer;
begin
res:=0;
for i:=1 to m do
for j:=1 to n do
begin
if a[i]=b[j] then f[i,j]:=g[i-2,j-2]+1;
if f[i,j]>res then res:=f[i,j];
g[i,j]:=max(g[i-1,j],g[i,j-1],f[i,j]);
end;
write(res);
end;
begin
init;
optimize;
end.