program MaxRostVybrPosl; const MAX = 100; type vektor = array [1..MAX] of integer; delka = 0..MAX; var A : vektor; {vstupujici posloupnost} DEL : delka; {delka skutecne vyuzite casti posloupnosti A} POM : vektor; {pomocne pole } { POM[I] je delka maximalni rostouci vybrane posloupnosti z posloupnosti A, ktera zacina na indexu I } MAXR : delka; {delka hledane posloupnosti} {pomocne promenne} I,J,K,I0 : integer; M : delka; begin { ----- vstup posloupnosti A ------------} {Je naprogramovan vstup z klavesnice. Ten vsak neni pro danou ulohu vubec vhodny, protoze vstupni posloupnost by mohla byt hodne dlouha. Nam vsak nejde o vstup a vystup, ale o algoritmus a praci s poli. } writeln('Zadej delku vstupujici posloupnosti - od 2 do 100'); readln(DEL); writeln('Zadavej vzdy jedno cislo na radku a stiskni enter:'); for I:=1 to DEL do begin writeln('Jeste ', DEL+1-I, ' cisel'); readln(A[I]); end; { ----- zaplneni pomocneho pole POM -----} { pole POM budeme zaplnovat od zadu } {inicializace } POM[DEL] := 1; MAXR := 1; for I:=DEL-1 downto 1 do begin M:=0; for J:=I+1 to DEL do if A[J]>A[I] then { A[J] muze byt za A[I] } if POM[J]>M then M:=POM[J]; { M je maximem z tech hodnot POM[J] J= I+1 ... DEL , pro nez plati A[J]>A[I] } POM[I]:= M+1; If POM[I]>MAXR then MAXR:=POM[I]; end; { ----- nalezeni a vystup hledane nejdelsi rostouci vybrane posloupnosti POM -----} { zde by pripadne mohla vystoupit vstupujici posloupnost } writeln('Hledana nejdelsi rostouci vybrana posloupnost ma delku', MAXR:4); writeln('Na kazde radce vystupuje vzdy '); writeln('nejprve index a pak hodnota prvku vybrane posloupnosti :' ); I:=1; while POM[I]<>MAXR do I:=I+1; {posloupnost zacina v indexu, kde POM nabyva hodnoty MAXR } writeln(I:4,A[I]:10); I0:=I; {index posledniho zjisteneho prvku hledane posl. } for K:= MAXR-1 downto 1 do begin while (POM[I]<>K) or (A[I]<=A[I0]) do I:=I+1; {dalsi prvek musi mit hodnotu POM[I] rovnu K a pri tom musi platit A[I]>A[I0] } I0:=I; writeln(I:4,A[I]:10); end; end.