Subsecvență de sumă maximă

Cerință:

Se dă un şir S[ ] = (s1, s2, .., sN) de lungime N. O subsecvenţă a şirului este de forma: (si, si+1, ..., sj) cu 1 ≤ i ≤ j ≤ N, iar suma subsecvenţei este si + si+1 + ... + sj. Se cere să se determine subsecvenţa de sumă maximă.

​

Rezolvare:

Soluția optimă folosește metoda programării dinamice. Construim un şir besti egal cu costul subsecvenţei de sumă maximă ce se termină pe poziţia i. Rezultă recurenţa următoare: besti = Max(besti-1 + si, si). Rezultă mai departe că si este sfârşitul unei subsecvenţe ce se extinde spre stânga cu subsecvenţa de sumă maximă ce se termină în si-1 doar dacă această subsecvenţă are suma pozitivă. În implementare nu este necesar să reţinem întregul vector best si nici șirul S, ci doar o variabilă, rezolvarea facându-se direct din citire, după cum se vede şi în sursă.  Complexitate: O(N) timp și O(1) memorie.

#include <iostream>

using namespace std;

int main() {

    int n, i, st, dr, maxx = -(1 << 29), sum = 0, poz = 1, x;

    cin >> n;

    for (i = 1; i <= n; i++) {

        cin >> x;

        if(sum < 0) {

            sum = x;

            poz = i;

        } else {

            sum += x;

        }

        if(sum > maxx) {

            maxx = sum;

            st = poz; 

           dr = i;

        }

    }

    cout << maxx << " " << st << " " << dr << "\n";

    return 0;

}