PROGRAM Posloupnost;
 CONST nmax=100;                        {Maximalni delka posloupnosti.}
       max=1000;                        {Maximalni hodnota clenu posl.}
 TYPE posl=ARRAY [1..nmax] OF INTEGER;
 VAR   a: posl;                         {Zde bude nahodna posloupnost,}
       i,n: INTEGER;                    {jejiz delka je n.}
       b,c: posl;                       {Zde bude nalezena podposloupnost.}

{ ****************        Nerekurzivni hledani       ****************** }
 PROCEDURE MaxRost1(VAR p:posl);
  VAR i,j: INTEGER;
       up: posl;                        {Ukazale na dalsi clen.}
 BEGIN
 {Urceni nejdelsi rostouci posl. zacinajici v danem a[i].}
   b[n]:=1; up[n]:=0;
   FOR i:=n-1 DOWNTO 1 DO BEGIN
     b[i]:=1; up[i]:=0;
     FOR j:=i+1 TO n DO
       IF ((b[j]+1>b[i])AND(a[j]>a[i])) THEN BEGIN
         b[i]:=b[j]+1;
         up[i]:=j;
       END
   END;
 {Nalezeni nejdelsi z nich.}
   j:=1;
   FOR i:=2 TO n-1 DO
     IF (b[i]>b[j]) THEN j:=i;
   b[1]:=a[j]; i:=1;
   WHILE (up[j]<>0) DO BEGIN
     i:=succ(i);
     j:=up[j];
     b[i]:=a[j];
   END;
   i:=succ(i);
   IF (i<=n) THEN b[i]:=0;
 END;

{ ****************         Rekurzivni hledani        ****************** }
 PROCEDURE MaxRost2(VAR p:posl);
  VAR q: posl;
      i,l,lm: INTEGER;
  PROCEDURE Mx(ii,jj:INTEGER);
   VAR i: INTEGER;
  BEGIN
    q[jj]:=a[ii];
    IF jj>lm THEN BEGIN
      lm:=jj;
      FOR i:=1 TO jj DO p[i]:=q[i];
    END;
    FOR i:=ii+1 TO n DO
      IF a[i]>a[ii] THEN Mx(i,jj+1);
  END;
 BEGIN
  lm:=0;
  FOR i:=1 TO n DO p[i]:=0;
  FOR i:=1 TO n-1 DO Mx(i,1);
 END;

BEGIN
{ **************** Cteni n a generovani posloupnosti ****************** }
  WRITE('Pocet clenu posloupnosti (<101), n=');
  READLN(n);
  RANDOMIZE;                            {Inicializace generatoru nahodnych}
  FOR i:=1 TO n DO                      {cisel a}
    a[i]:=1+RANDOM(max);                {generovani nahodne posloupnosti.}
  WRITELN('Vygeneroval jsem posloupnost:');
  FOR i:=1 TO n DO WRITE(a[i]:5);
  WRITELN;
{ ****************  Hledani a vypis podposloupnosti  ****************** }
  WRITELN('Nerekurzivni hledani');
  MaxRost1(b);
  WRITELN('Nejdelsi rostouci podposloupnost:');
  i:=1;
  REPEAT
    WRITE(b[i]:5);
    i:=succ(i)
  UNTIL((b[i]=0)OR(i>n));
  WRITELN;
  WRITELN('Rekurzivni hledani');
  MaxRost2(c);
  WRITELN('Nejdelsi rostouci podposloupnost:');
  i:=1;
  REPEAT
    WRITE(c[i]:5);
    i:=succ(i)
  UNTIL((c[i]=0)OR(i>n));
  WRITELN;
  READLN;
END.