Određivanje maksimalne sume uzastopnog podniza

Pretpostavimo da je dat niz celih brojeva:

{3, 5, -10, -34, 16, 2}

Za niz A od n brojeva, uzastopni podniz je niz koji se sastoji od nula ili više susednih elemenata niza A. U datom primeru {5, -10, -34} jeste uzastopni podniz, a {3, -34, 2} nije, jer su preskočeni neki elementi.

Pošto i prazan podniz (bez elemenata) računamo kao uzastopni, njegov zbir 0 je najmanji mogući rezultat. Za dati niz rešenje je 18, a dobija se od podniza {16, 2}.

Video: algoritam po definiciji problema

Video kroz animaciju objašnjava algoritam koji određuje maksimalnu sumu podniza polazeći od same definicije problema, odnosno ispitivanjem svih podnizova.

Svi uzastopni podnizovi

Da bismo našli najveći zbir, najpre posmatramo sve uzastopne podnizove:

{}, {3}, {3, 5}, {3, 5, -10}, {3, 5, -10, -34}, {3, 5, -10, -34, 16}, {3, 5, -10, -34, 16, 2}
{5}, {5, -10}, {5, -10, -34}, {5, -10, -34, 16}, {5, -10, -34, 16, 2}
{-10}, {-10, -34}, {-10, -34, 16}, {-10, -34, 16, 2}
...

Svaki podniz je određen početnom pozicijom poc i krajnjom pozicijom kr. Zato koristimo ugnježdene petlje: spoljašnja menja početak, srednja menja kraj, a unutrašnja ispisuje elemente od početka do kraja.

#include <iostream>
using namespace std;

int main()
{
    int niz[] = {3, 5, -10, -34, 16, 2};
    int n = sizeof(niz) / sizeof(niz[0]);   // broj elemenata niza

    // poc - početak podniza, kr - kraj podniza
    for (int poc = 0; poc < n; poc++)
    {
        for (int kr = poc; kr < n; kr++)
        {
            // Ispis podniza od pozicije poc do pozicije kr
            for (int j = poc; j <= kr; j++)
            {
                cout << niz[j] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

Za niz od 6 elemenata program ispisuje 21 neprazan podniz, jer je 6 · 7 / 2 = 21.

Rešenje po definiciji — O(n³)

Umesto ispisa, za svaki podniz računamo zbir i pamtimo najveći. Najjednostavnije je da se zbir računa iz početka, posebnom petljom:

#include <iostream>
using namespace std;

int main()
{
    int niz[] = {3, 5, -10, -34, 16, 2};
    int n = sizeof(niz) / sizeof(niz[0]);

    int M = 0;   // najveći zbir; 0 odgovara praznom podnizu

    for (int poc = 0; poc < n; poc++)
    {
        for (int kr = poc; kr < n; kr++)
        {
            // Zbir podniza od poc do kr računamo iz početka
            int z = 0;
            for (int j = poc; j <= kr; j++)
            {
                z = z + niz[j];
            }

            if (z > M)
                M = z;
        }
    }

    cout << "M = " << M << endl;
    return 0;
}

Tri ugnježdene petlje daju složenost O(n³). Za niz od 1000 elemenata to je oko 170 miliona sabiranja.

Poboljšanje — O(n²)

Unutrašnja petlja nije potrebna. Podniz od poc do kr dobija se kada podnizu od poc do kr − 1 dodamo samo jedan element, pa je i njegov zbir prethodni zbir uvećan za niz[kr]. Na primer, zbir za {3, 5, -10, -34} jednak je zbiru za {3, 5, -10} uvećanom za -34.

#include <iostream>
using namespace std;

int main()
{
    int niz[] = {3, 5, -10, -34, 16, 2};
    int n = sizeof(niz) / sizeof(niz[0]);

    int M = 0;   // najveći zbir; 0 odgovara praznom podnizu

    for (int poc = 0; poc < n; poc++)
    {
        int z = 0;   // zbir podniza koji počinje na poziciji poc

        for (int kr = poc; kr < n; kr++)
        {
            // Podniz [poc, kr] dobijamo kada podnizu [poc, kr - 1]
            // dodamo jedan element, pa zbir samo uvećamo za niz[kr].
            z = z + niz[kr];

            if (z > M)
                M = z;
        }
    }

    cout << "M = " << M << endl;
    return 0;
}

Sada su ostale dve petlje, pa je složenost O(n²).

Specijalni slučajevi

• Svi članovi niza su pozitivni: najveći zbir ima ceo niz, jer svaki dodati element povećava zbir.
• Svi članovi niza su negativni: svaki neprazan podniz ima negativan zbir, pa je najbolji prazan podniz sa zbirom 0. Ako zadatak zahteva da podniz ima bar jedan element, rešenje je najveći (najmanje negativan) element niza.

Kako doći do linearnog rešenja?

I rešenje O(n²) ponavlja mnogo posla. Umesto da za svaki početak prolazimo kroz ostatak niza, posmatrajmo krajnju poziciju: koji je najveći zbir podniza koji se završava baš na poziciji i?

• Takav podniz je ili najbolji podniz koji se završava na poziciji i − 1, produžen elementom niz[i],
• ili počinje iznova, ako je prethodni zbir negativan i samo bi smanjio rezultat.

Tako je za svaku poziciju dovoljna jedna operacija, a ceo niz se prođe samo jednom. To je Kadaneov algoritam, složenosti O(n), opisan na sledećoj strani.

Složenost

• Rešenje po definiciji (tri petlje): O(n³)
• Rešenje sa pamćenjem zbira (dve petlje): O(n²)
• Kadaneov algoritam: O(n)

Problem se često javlja u računarskoj biologiji, pri analizi DNK i proteinskih sekvenci, kao i u analizi finansijskih podataka (na primer, period sa najvećim ukupnim dobitkom).