Cel mai lung subsir crescator dintr-un sir

O problema clasica de Programare Dinamica este determinarea celui mai lung subsir strict crescator dintr-un sir de numere. Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, in ordinea in care acestea apar in sir.

Exemplu: pentru sirul 24 12 15 15 8 19 raspunsul este sirul 12 15 19.

Se observa ca daca incercam o abordare greedy nu putem stabili nici macar elementul de inceput intr-un mod corect.
Se poate rezolva si cu un algoritm care alege toate combinatiile de numere din sir, valideaza ca sirul obtinut este strict crescator si il retine pe cel de lungime maxima, dar aceasta abordare are complexitatea temporala O(2^N). Cu optimizari este posibil sa se ajunga la O(N!).

O metoda de rezolvare mai eficienta foloseste Programarea Dinamica. Incepem prin a stabili pentru fiecare element lungimea celui mai lung subsir strict crescator care incepe cu primul element si se termina in elementul respectiv. Numim aceasta valoare best(i) si aplicam formula recursiva best(i)= 1+ max(best(j)), cu j < elem(i).

Aplicand acest algoritm obtinem:
elem 24 12 15 15 8 19
best 1 1 2 2 1 3

Pentru 24 sau 12 nu exista nici un alt element in stanga lor strict mai mici decat ele, de aceea au best egal cu 1. Pentru elementele 15 se poate gasi in stanga lor 12 strict mai mic decat ele. Pentru 19 se gaseste elementul 15 strict mai mic decat el. Cum 15 deja este capat pentru un subsir-solutie de 2 elemente, putem spune ca 19 este capatul pentru un subsir-solutie de 3 elemente.
Cum pentru fiecare element din multime trebuie sa gasim un element mai mic decat el si cu best maxim, avem o complexitate O(N) pentru fiecare element. In total rezulta o complexitate O(N^2). Se pot obtine si rezolvari cu o complexitate mai mica folosind structuri de date avansate.

Pentru a gasi care sunt elementele ce alcatuiesc subsirul strict crescator putem sa retinem si o „cale de intoarcere”. Reconstructia astfel are complexitatea O(N). Exemplu: subproblema care se termina in elementul 19 are subsirul de lungime maxima 3 si a fost calculata folosind subproblema care se termina cu elementul 15 (oricare din ele). Subsirul de lungime maxima care se termina in 15 a fost calculat folosindu-ne de elementul 12. 12 fiind cel mai mic element din subsir marcheaza sfarsitul reconstructiei.

Programul in C este:

// sir de n numere se cere implementarea unui progr care det cel mai lung sir crescator O(n^2)

#include "stdio.h"

int main () {

int v [] = {24, 12, 15, 15, 8, 19}, n = 6;
int s[6], m =0, prec[6], l=0, best[6];
int i,j,k;
for(i=0; i < n;i++) {
best[i]=0;
prec[i]=-1;
}
best[0]=1;
for(i=1; i < n;i++) {
int max = 0;
for(j=0;j < i; j++) {
if(v[j] < v[i] && max < =v[j]) {
max = v[j];
best[i]=1+best[j];
prec[i]=j;
}
if(v[j]==v[i]) best[j]=best[i];
}
if(best[i]==0) best[i]=1;

}

int maxbest =0;
for(i=0; i < n; i++)
if(best[i] > maxbest)
maxbest = best[i];
j=0;
for(i=n-1; i > =0;i--)
if(best[i]==maxbest) {
s[j++]=v[i];
if(prec[i] > =0)
s[j++]=v[prec[i]];
i = prec [i];
maxbest=maxbest - 2;
}
for(i=j-1; i > =0; i--)
printf("%d ", s[i]);
printf("\n");
return 0;
}