Kadaneov algoritam za maksimalnu sumu uzastopnog podniza

Algoritam po definiciji problema ispituje sve podnizove i ima kvadratnu (ili čak kubnu) složenost. Kadaneov algoritam rešava isti problem u jednom prolazu kroz niz, pa je linearne složenosti O(n).

Posmatrajmo ponovo niz:

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

---

Ideja algoritma

Pamtimo dve vrednosti:

• maxTrenutni – najveći zbir podniza koji se završava na tekućoj poziciji,
• maxUkupno – najveći zbir pronađen od početka niza.

Obe vrednosti na početku postavljamo na 0 (zbir praznog podniza). Zatim za svaki element niza:

1. tekući element dodamo na maxTrenutni, čime produžavamo najbolji podniz koji se završavao na prethodnoj poziciji;
2. ako je maxTrenutni veći od maxUkupno, ažuriramo maxUkupno;
3. ako je maxTrenutni postao negativan, postavljamo ga na 0. Negativan zbir bi samo smanjio svaki sledeći podniz, pa je bolje da sledeći podniz počne iznova. Zbir 0 odgovara praznom podnizu.

---

Implementacija (C++)

#include <iostream>
using namespace std;

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

    int maxTrenutni = 0;   // najveći zbir podniza koji se završava na tekućoj poziciji
    int maxUkupno = 0;     // najveći zbir pronađen od početka (0 = prazan podniz)

    // Pomeramo tekuću poziciju od prvog do poslednjeg elementa
    for (int i = 0; i < n; i++)
    {
        // Produžavamo najbolji podniz koji se završavao na prethodnoj poziciji
        maxTrenutni = maxTrenutni + niz[i];

        // Ako je dobijeni zbir veći od dosadašnjeg maksimuma, pamtimo ga
        if (maxTrenutni > maxUkupno)
            maxUkupno = maxTrenutni;

        // Negativan zbir samo bi umanjio sledeće podnizove,
        // pa je bolje početi iznova od praznog podniza (zbir 0)
        if (maxTrenutni < 0)
            maxTrenutni = 0;
    }

    cout << "Maksimalni zbir uzastopnog podniza je " << maxUkupno << endl;
    return 0;
}

Izvršavanje korak po korak

Element	maxTrenutni + element	maxTrenutni posle provere	maxUkupno
3	3	3	3
5	8	8	8
-10	-2	0	8
-34	-34	0	8
16	16	16	16
2	18	18	18

Posle elementa -10 zbir postaje negativan, pa se tekući podniz „prekida” i kreće iznova. Najveći zbir je 18, za podniz {16, 2}.

---

Varijanta: podniz mora imati bar jedan element

Gornja verzija dozvoljava prazan podniz, pa za niz u kome su svi elementi negativni vraća 0. Mnogi zadaci traže da podniz ima bar jedan element. Tada polazimo od prvog elementa, a za svaku sledeću poziciju biramo bolje od dve mogućnosti: da produžimo prethodni podniz ili da počnemo novi od tekućeg elementa.

#include <iostream>
#include <vector>
#include <algorithm>   // za funkciju max
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<long long> niz(n);
    for (int i = 0; i < n; i++)
        cin >> niz[i];

    // Podniz mora imati bar jedan element, pa krećemo od prvog
    long long maxTrenutni = niz[0];
    long long maxUkupno = niz[0];

    for (int i = 1; i < n; i++)
    {
        // Ili nastavljamo prethodni podniz, ili počinjemo novi od niz[i]
        maxTrenutni = max(maxTrenutni + niz[i], niz[i]);

        maxUkupno = max(maxUkupno, maxTrenutni);
    }

    cout << maxUkupno << endl;
    return 0;
}

Za niz {-5, -2, -7} ova verzija vraća -2, a prva verzija 0.

---

Složenost

• Vremenska složenost: O(n) – svaki element obrađuje se tačno jednom
• Prostorna složenost: O(1) – pored niza čuvaju se samo dve promenljive

Kadaneov algoritam je jednostavan primer dinamičkog programiranja: rešenje za poziciju i gradi se iz rešenja za poziciju i − 1.