h3. (problema grea, clasa a 10-a)

Pentru a afla numarul maxim palindrom care este subsir al numarului $N$ vom utiliza metoda programarii dinamice. Fie {$L{~i,j~}$} lungimea maxima a unui numar palindrom care se gaseste intre pozitiile $i$ si $j$ din numarul {$N$}. In momentul in care construim tabloul $L$ consideram ca un numar poate incepe si cu cifra {$0$}. Initial, {$L{~i,i~}$} = 1, pentru orice $i$ de la $1$ la numarul de cifre ale lui {$N$}. Vom calcula elementele tabloului $L$ crescator in functie de marimea intervalelor {$(i,j)$}. Daca consideram ca {$LEFT{~c,i~}$} este cea mai mica pozitie {$≥ i$} in care apare cifra $c$ in numarul $N$ si {$RIGHT{~c,i~}$} cea mai mare pozitie {$≤ i$} in care apare $c$ in numarul $N$, avem urmatoarea relatie de recurenta:
{$L{~i,j~}$} = maxim({$L{~i+1,j~}$}, {$L{~i,j-1~}$}, {$L{~i+1, RIGHT[N[i]][j]-1~} + 2$}, {$L{~LEFT[N[j]][i]+1, j-1~} + 2$}), unde prin {$N{~i~}$} s-a notat a $i$-a cifra a numarului {$N$}. Relatia de recurenta trateaza urmatoarele cazuri:
 
* nu folosim cifra a $i$-a in solutia optima
* nu folosim cifra a $j$-a in solutia optima
* folosim cifra a $i$-a ( notata $c$ ) in solutia optima. Pentru ca numarul intre $i$ si $j$ sa fie palindrom, este suficient sa aflam ultima pozitie $p$ inainte de $j$ a cifrei c, solutia optima intre $i$ si $j$ obtinandu-se din solutia optima intre $i+1$ si $p-1$ la care adaugam 2 cifre ( cele din capete ).
* folosim cifra a $j$-a ( notata $c$ ) in solutia optima. Se trateaza similar.
 
Daca tablourile $LEFT$ si $RIGHT$ sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul $L$ in complexitate {$O(NR_CIF^2^)$}, unde $NR_CIF$ este numarul de cifre ale lui {$N$}. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca dorim sa cautam aceasta solutie intre pozitiile {$i$} si {$j$} si {$L{~i,j~}$} = {$X$}. Vom pune la capetele solutiei cea mai mare cifra $c$ care indeplineste:
{$L{~LEFT[c,i]+1,RIGHT{@[c,j]@}-1~}$} = {$X-2$}.
 
 
In final, eliminam {$0$}-urile terminale ( de la ambele capete ale numarului palindrom ) si afisam acest numar. De precizat ca un algoritm de complexitate {$O(NR_CIF^2^)$} si constanta $10$ ar fi obtinut in jur de 50 de puncte.
 

h2. 'Distincte':problema/distincte
h3. (problema medie, clasele 11-12)