Reconst
Vom considera fiecare intrebare pusa ca fiind un interval de pozitii pentru care este necesar sa aiba o anumita suma data. O prima observatie care ne va ajuta sa rezolvam problema este ca daca nu avem doua intervale care sa inceapa pe aceeasi pozitie putem gasi foarte usor un algoritm greedy care sa furniezeze un raspuns corect. Parcurgem sirul de la ultima pozitie inspre prima, si vom considera ca toate elementele sale au valoarea 0, mai putin cele care sunt capatul de inceput al unui interval. Pentru aceste pozitii, vom considera valoarea lor ca fiind acel numar egal cu diferenta intre suma data a intervalului si suma valorilor deja alese pentru celelalte pozitii care fac parte din interval. In continuare vom analiza cazul in care exista cel putin o pereche de intervale care au acelasi capat de inceput. Fie doua intervale [A, B] si [A, C]. Daca B = C, atunci putem pur si simplu sa nu luam in calcul unul din cele doua intervale. In caz contrar putem considera ca B < C fara a restrange generalitatea. Fie S1 suma data pentru primul interval si S2 suma data pentru cel de-al doilea. Este destul de simplu de observat ca in loc de intervalul [A, C] de suma S2, putem sa consideram intervalul [B+1, C] de suma S2-S1. Repetand acest pas atat timp cat este nevoie vom ajunge la o configuratie in care nu exista doua intervale care sa aiba acelasi capat de inceput. Acest algoritm are complexitatea O(M2), deoarece fiecare segment poate fi inlocuit cu un alt segment mai mic de maxim M ori.
