Numere2 - toate sumele posibile

[•MacWonk]

Salut!
Am si eu o intrebare: cum formez toate sumele posibile cu niste numere date.
De exemplu problema "numere2":

Sa consideram un sir de n numere naturale nenule a=(a1, a2, ..., an).
Să se determine lungimea maxima a unui sir de numere naturale de forma p, p+1, p+2, ..., p+k cu proprietatea ca fiecare termen din sir se poate obtine ca suma a unor numere din sirul a. La o suma un numar din sirul a poate participa o singura data.

[•SebiSebi]

Programare dinamica: ceva asemanator cu problema rucsacului.  
d[ i ][ s ] = 1, daca se poate forma suma s cu o submultime a primelor i elemente;
Poti sa reduci memoria folosita la O(S), iar complexitatea va fi O(N*S) unde N este numarul de elemente si S suma tuturor elementelor.

[•MacWonk]

Multumesc pentru raspuns!