Cod sursa(job #670754)

Utilizator pongraczlajosLajos Pongracz pongraczlajos Data 29 ianuarie 2012 23:16:06
Problema Subsir crescator maximal Scor 70
Compilator fpc Status done
Runda Arhiva educationala Marime 0.62 kb
var a,len,poz:array[1..100005] of longint;
    n,i,j,max,imax:longint;
    f:text;

begin
assign(f,'scmax.in');
reset(f);
readln(f,n);
for i:=1 to n do
 read(f,a[i]);
close(f);

assign(f,'scmax.out');
rewrite(f);

len[n]:=1;
poz[n]:=-1;
max:=1;
imax:=n;
for i:=n-1 downto 1 do begin
 len[i]:=1;
 poz[i]:=-1;
 for j:=i+1 to n do
  if ((a[i]<a[j]) and (len[i]<len[j]+1)) then begin
   len[i]:=len[j]+1;
   poz[i]:=j;
   if (len[i]>max) then begin
    max:=len[i];
    imax:=i;
   end;
  end;
end;

writeln(f,max);
i:=imax;
while (i<>-1) do begin
 write(f,a[i],' ');
 i:=poz[i];
end;

close(f);
end.