Subsecvenţa de sumă maximă

Popa Sebastian

Enunț

Se dă un şir de \(n\) numere întregi \([a_1, a_2, \ldots, a_n]\). Să se determine o subsecvenţă nevidă \([a_i, a_{i+1}, \ldots, a_j]\) care să aibă suma elementelor maximă.

Observații

Soluțiile naive in \(O(n^3)\) sau \(O(n^2)\) (folosind sume partiale) nu le vom discuta, deoarece sunt triviale. Complexitatea dorită este \(O(n)\).

Soluția 1 - Algoritmul lui Kadane

Fie best[i] suma maximă a unei subsecvențe ce se termină cu elementul \(i\). Pentru \(i = 1\), best[1] va fi egal cu a[1]. Pentru \(i\) de la \(2\) la \(n\) vom folosi următoarea formulă: best[i] = max(a[i], best[i - 1] + a[i]). Raționamentul din spatele acestei formule este foarte bine explicat aici, dar ea poate fi și demonstrată prin inducție matematică. Maximul valorilor din best reprezintă valoarea căutată.

În implementarea codului putem evita folosirea vectorului auxiliar best, deoarece, la fiecare pas, avem nevoie doar de o valoare, cea anterioară.


int ssm(const vector<int> &v)
{
    int maxim = INT_MIN, s = 0;
    for (int i = 0; i < (int)v.size(); i++)
    {
        s += v[i]; // adaugam elementul curent la maximul local
        rez = max(rez, aux); // actualizam maximul global
        if (s < 0) // daca maximul local e negativ atunci este mai bine sa nu il includem, deci maximul local devine 0
            s = 0;
    }
    return maxim; // returnam rezultatul
}

Soluția 2

Fie aux[i] = a[1] + a[2] + ... + a[i] și best[i] suma maximă a unei subsecvențe ce se termină cu elementul \(i\). Pentru fiecare poziție \(i\) de la \(1\) la \(n\), best[i] va lua valoarea aux[i] - aux[j], unde \(j\) este o pozitie mai mica decat \(i\) pentru care aux[j] este minim. Pentru aux[j] minim, expresia aux[i] - aux[j] este maximă.
Se poate evita folosirea vectorilor auxiliari, deoarece la fiecare pas este nevoie doar de valorile anterioare.


int ssm(const vector<int> &v)
{
    int rez = v[1], // maximul global
     minim = min(0, v[1]), //suma partiala minima
      ps = v[1]; // suma partiala
    for (int i = 1; i < (int)v.size(); i++)
    {
        ps += v[i]; //actualizam suma partiala
        minim = min(minim, ps); //  actualizam minimul
        rez = max(rez, ps - minim); //actualizam rezultatul
    }
    return rez;
}

Aplicații