h2. 'Consir':problema/consir

Sa presupunem ca dorim sa aflam rezultatul pentru secventa maximala $1, 2 ... M$. Fie $F{~1~}, F{~2~}, ... F{~M~}$ frecventele numerelor de la $1$ la $M$. Sa construim acum un vector $P$ cu semnificatia $P{~i~} = F{~1~}* F{~2~} * ... * F{~M~}$. Datoria faptului ca rezultatul este mai mic decat $2^63^$ este clar ca nu avem mai mult de 63 de pozitii pentru care $F{~i~}>1$

Sa presupunem ca dorim sa aflam rezultatul pentru secventa maximala $1, 2 ... M$. Fie $F{~1~}, F{~2~}, ... F{~M~}$ frecventele numerelor de la $1$ la $M$ (numarul de aparitii). Sa construim acum un vector $P$ cu semnificatia $P{~i~} = F{~1~}* F{~2~} * ... * F{~M~}$. Datoria faptului ca rezultatul este mai mic decat $2^63^$ este clar ca nu avem mai mult de 63 de pozitii pentru care $F{~i~}>1$  la fiecare pas trebuie sa updatam subsecventele care se termina intr-o pozitie cu $F{~i~}>1$. Algoritmul in pseudocod pentru a calcula vectorul $Res$ cu semnificatia $Res{~i~}$ egal cu numarul de consiruri de lungime $i$ devine
 
== code(c) |
Res[M] = P[M];
pentru i = n-1, 1 executa
   Res[i] = Res[i+1] + P[M]/P[M-i];
   pentru j astfel incat F[j] >= 2 si j >= i+1
       Res[i] = Res[i] - P[j]/P[j-i-1] + P[j]/P[j-i];
   sfarsit pentru
sfarsit pentru
==

h2. 'Polig':problema/polig