Subsir100
Vom calcula numarul de subsiruri "interesante" din sirul obtinut prin ordonarea sirului dat folosind metoda programarii dinamice. Corectitudinea algoritmului este data de faptul ca, numarul de subsiruri "interesante" din sirul dat este egal cu numarul de subsiruri "interesante" din sirul obtinut prin ordonarea sirului dat, deoarece exista o bijectie intre multimea subsirurilor "interesante" din sirul dat si multimea subsirurilor "interesante" din sirul obtinut prin ordonarea sirului dat (Tema demonstratia).
Fie A[1...N] sirul obtinut prin ordonarea sirului dat, iar X[i] numarul de subsiruri "interesante" din sirul A[i...N], oricare ar fi i un numar natural nenul cu proprietatea i ≤ N.
Evident X[N] = 1 si X[i] = X[i+1] + X[j] + 1, unde j este cel mai mic numar natural nenul ( i < j ≤ N ) cu proprietatea ca A[j] ≠ A[i]. In cazul in care nu exista un astfel de j, adunam 0 in loc de X[j]. Relatia de recurenta se explica astfel:
Numarul subsirurilor "interesante" din A[i...N] este egal cu numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i], plus numarul subsirurilor "interesante din" A[i...N] care il contin pe A[i]. Iar numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i] este egal cu numarul subsirurilor "interesante" din A[i+1...N] ( A[i+1...N] nu il contine pe A[i], iar aici ma refer la termenul A[i] si nu la valoarea lui). Pentru a obtine toate subsirurile "interesante" din A[i...N] care il contin pe A[i] trebuie sa eliminam din sirul A[i...N] toti termenii care au valoarea egala cu valoarea lui A[i] ( Intr-un subsir "interesant" toate valorile sunt distincte ) si sa il adaugam pe A[i] la inceputul fiecarui subsir "interesant" din sirul ramas. La acestea se adauga sirul care contine un singur termen si anume pe A[i]. Raspunsul cautat va fi in X[1].
Desi complexitatea determinarii sirului X este O(N), complexitatea finala este O(N*logN), datorita sortarii sirului dat.
