====== 9. cvičení - 27.11.2009 ======

===== Co bylo? =====

  * informace k zadání nových [[domaci-ulohy|domácích úloh]]
    * Cesta králem na šachovnici (délka)
    * Odstavcovač
    * Kontrola uzávorkování
    * Sokoban
  * [[domaci-ulohy#numericke_integrovani|ukázka řešení domácí úlohy 2]]
  * upozornění: **téma a krátká specifikace zápočťáku do konce listopadu**
  * modulární programování - ''unit'', ''interface'', ''implementation''
  * dynamické programování
    * násobení mnoha matic - optimální uzávorkování matic pro minimalizaci počtu násobení prvků matic
      * ukázkové zdrojáky ([[materialy|doc. Pavel Töpfer]]) - rychle odspodu [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/SOUCMAT2.PAS|dynamicky]], pomalu odshora [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/SOUCMAT1.PAS|rekurzivně]]
    * nejdelší rostoucí podposloupnost - ukázkový zdroják, viz níže
  * [[cviko8#inkrementalni_vypocty|inkrementální výpočty]]
    * spojitá podposloupnost celých čísel s největším součtem

<code pascal>
program lis;
{
Nejdelsi rostouci podposloupnost,
aneb Longest Increasing Subsequence (LIS)

Mame posloupnost cisel A, chceme spocitat delku LIS v A.

Priklad: pro A = [ 6, 3, 6, 10, 8, 9, 10, 10, 4, 1, -1 ] vrati 5.
}

const
  MAX=100;

function delka_lis(var A : array of integer; delka : integer) : integer;
var
  { Q[i] - delka LIS koncici v A[i] }
  Q : array[0..MAX-1] of integer;
  max : integer;
  j, k : integer;
begin
  { inicializace prvku Q na 1 - jednoprvkove podposl. maji delku 1 }
  for k := 0 to delka-1 do
  begin
    Q[k] := 1;
  end;
  for k := 0 to delka-1 do
  begin
    { chceme delku nejdelsi LIS koncici v A[j], na kterou
      lze napojit A[k] }
    max := 0;
    for j := 0 to k-1 do
    begin
      if ((A[k] > A[j]) AND (Q[j] > max)) then
      begin
        max := Q[j];
      end;
    end;
    { LIS prodlouzime o aktualni prvek A[k] }
    Q[k] := max + 1;
  end;
  { pouze uz jen najdeme maximum v Q }
  for k := 0 to delka-1 do
  begin
    if (Q[k] > max) then
    begin
      max := Q[k];
    end;
  end;
  delka_lis := max;
end;

var
  posloupnost : array[0..MAX-1] of integer;
  i : integer;
  N : integer; {delka posloupnosti}
begin
  readln(N);
  if (N > MAX) then
  begin
    N := MAX;
    writeln('Pozor: bude zpracovano najvys ', MAX, ' prvku.');
  end;
  for i := 0 to N-1 do
  begin
    readln(posloupnost[i]);
  end;
  writeln(delka_lis(posloupnost, N));
end.

</code>