Problema Subs

[•darkseeker]

Enuntul problemei se poate gasi aici http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1233.

Rezolvarea mea obtine 90 de puncte, iau wa pe testul maxim. Ideea de rezolvare se bazeaza pe cea prezentata in cartea "Psihologia concursurilor de informatica ".

Folosesc 2 matrici alocate dinamic Q si D cu urmatoarea semnificatie:

Cod:

D[i][j] = diferenta minima care se poate obtine cu un subsir de lungime maxima terminat in Q[i][j] 

In continuare voi detalia constructia matricii Q. Pe linia 0 din matricea Q construiesc exact vectorul explicat in cartea mentionata, iar pe fiecare coloana retin numerele suprascrise in ordinea suprascrierii lor, inclusiv numarul curent, numerele de pe fiecare coloana a matricei fiind sortate in mod descrescator .

Cand suprascriu elementul Q[0][ i] cu un alt element, caut pe coloana i-1 pozitia pe care se gaseste cel mai mare element mai mic sau egal cu Q[0][ i] . Notez aceasta pozitie cu x iar pozitia pe care o ocupa elementul Q[0][ i] in coloana i a matricei cu y.

Folosesc urmatoarea relatie de recurenta

Cod:

D[y][i] = min(max(Q[0][i] - Q[j][i -1],D[j][i -1]) ), x <= j <= numarul d elemente de pe colaona i-1 a matricii Q; 

Dupa cum este mentionat in carte, lungimea celui mai lung subsir comun este chiar numarul de elemente al vectorului Q, iar in cazul meu diferenta minima este
min (D[lungimeSir][ i]), 1 < = i <= numar de elemente pe coloana lungimeSir.

Astept orice sugestie / orice contraexemplu si sper ca va fi utila/util. Multumesc anticipat .