h3. Soluţie:

Să o rezolv întâi...

Voi face un desen pentru explicaţii. :)
 
== code(cpp) |
Algoritmul este:
    // S[] şirul iniţial de numere iar N lungimea sa
    // (last, i] este intervalul de lungime maximă care se termină în i a cărui sumă nu depăşeşte M
    sum  = 0;
    last = 0;
    // indicii head si tail ai dequeului
    deque[head = tail = 1] = 0;
    pentru i = 1, N execută
        sum += S[i];
        temp = bst[ deque[tail] ];
        cât timp (head <= tail) şi S[ deque[tail] ] <= S[i] execută
            temp = Min(temp, iMin[tail]);
            tail --;
        sfcâttimp
        // adaug poziţia i la deque
        tail ++;
        deque[tail] = i;
        // actualizez iMin[]
        iMin[tail]  = temp;
        // actualizez T[]
        update(T, tail, iMin[tail] + S[i]);
 
        cât timp (head <= tail) şi (sum > M) execută
            sum -= S[last];
            dacă (deque[head] == last) atunci
                head ++
            sfdacă
            iMin[head] = query(bst, last, deque[head] - 1);
            update(T, head, M[head] + S[ deque[head] ]);
            last ++;
        sfcâttimp
        // reţin optimul pentru poziţia curentă
        bst[i] = query(T, head, tail);
    sfpentru
    scrie bst[N];
Sfârşit.
==

h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)