Cod sursa(job #203639)

Utilizator 7RaduRadu Antohi 7Radu Data 18 august 2008 09:22:20
Problema Subsir crescator maximal Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 0.87 kb
program Scmax;
var
  fl : text;
  a, b, s : array[0..100010] of longint;
  n, i, j, k : integer;
begin
   assign(fl,'scmax.in');
   reset(fl);
   readln(fl,n);
   for i := 1 to n do
      begin
         read(fl,a[i]);
         b[i] := n+1;
         s[i] := 0;
      end;
   close(fl);

   s[n] := 1;
   b[n] := n+1;
   for i := n downto 1 do
       for j := i+1 to n do
          begin
             if (a[j] > a[i]) and (s[j]+1 > s[i]) then
                begin
                   s[i] := s[j]+1;
                   b[i] := j;
                end;
            end;

   k := 1;
   for i := 1 to n do
     if s[i] > s[k] then
        k := i;

   assign(fl,'scmax.out');
   rewrite(fl);
   writeln(fl,s[k]);
   while b[k] <> n+1 do
      begin
         write(fl,a[k],' ');
         k := b[k];
      end;
   write(fl,a[k]);
   close(fl);
end.