ODREĐIVANJE MAKSIMALNE SUME UZASTOPNOG PODNIZA

Pretpostavimo da imamo neki niz celih brojeva:

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

Problem koji treba rešiti: Iz posmatranog niza brojeva odrediti maksimalnu sumu svih uzastopnih podnizova. 
Za niz A od n brojeva, neprekidni podniz niza A je drugi niz koji se sastoji ili od nula ili više uzastopnih elemenata niza A.
U prethodnom primeru npr. niz:
{ 5,-10,-34}
je neprekidan, dok
{ 3,-34, 2}
to nije


Algoritam određivanja maksimalne sume uzastopnog podniza-video

Video objašnjava detaljno kroz animaciju opisani algoritam koji određuje maksimalnu sumu podniza za zadat niz brojeva. Algoritam polazi od same definicije problema i kvadratne je složenosti.
Uočimo sve podnizove, da bi od njih formirali zbirove i našli maksimalan​:

{}, {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}
​
itd.

​Da bi ostvarili promenu početne pozicije, a zatim za određenu početnu poziciju vršili pomeranje kroz niz koristimo ugnježdene for petlje.
​Sve podnizove bi mogli da dobijemo koristeći for petlju u kojoj za određenu tekuću poziciju početnog elementa redom menjamo krajnju poziciju i ispišemo sve članove niza od početne do  krajnje pozicije:
int niz[]={ 3,5,-10,-34,16 2};
…
for(int kr=poc; kr < n; kr++)
{
for(int j=poc; j<=kr; j++)
{
printf("%2d",niz[j]);
}
printf("/n");
}
​I sada bi ovaj kod ubacili u telo još jedne for petlje koja menja početak od 0 do n.
for(int poc=0; poc <= n; poc++)
{
for(int kr=poc; kr < n; kr++)
{
for(int j=poc; j<=kr; j++)
{
printf("%2d",niz[j]);
}
 printf("/n");
}
}


​S obzirom da se traže zbirovi tih podnizova i to maksimalni zbir, unutrašnja for petlja se može izbeći jer se uvek pamti privremeni zbir trenutnog podniza, pa se za sledeći element u for petlji čija je žuta bila ugnježdena on samo doda prethodnom zbiru i onda se poredi sa trenutnim maksimumom.

Dakle:
#include < stdio.h >
#include < stdlib.h >

int main()
{
const int n = 6;
int niz[]={ 3,5,-10,-34,16 2};
int z=0;
int M=0;
for(int poc=0; poc < n; poc++)
{
z=0;
for(int kr=poc; kr < n; kr++)
{
z=z+niz[kr];
if(z>M)
M=z;
}
printf("/n");
}
printf("M=%3d",M);
}

Specijalan slučaj 1: Ako su svi članovi niza pozitivni

​U tom slučaju je očigledno da će najveća suma biti od podniza sa najviše elemenata, a to je sam taj niz.

Specijalan slučaj 2: Ako su svi članovi niza negativni​

​U tom slučaju je očigledno da će najveća suma biti od podniza sa najmanje elemenata, a to je prazan niz.
Zadatak se može rešiti i paravljenjem funkcije koja određuje maksimum podniza, za odeđenu fiksnu početnu poziciju, a onda se kroz petlju u glavnoj (main) funkciji poziva prethodno kreirana funkcija i kao parametri šalju početna pozicija i sam početni niz, kao i broj elemenata.
Ovaj algoritam je spor i kvadratne je složenosti. Treba uočiti da se unutrašnjom petljom prolaze kroz skoro sve elemente niza kao u prethodnom ciklusu, samo bez prvog člana, tj. za 1 manje.
 Npr. ako se u jednoj iteraciji spoljašnje petlje prođe kroz sledeće elemente:

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

Onda bi se u sledećoj prošlo kroz:

5, -10, -34, 16 , 2
​
Dakle zbir u drugoj iteraciji može da se dobije kao zbirPrveIteracije – 3.
Kroz spoljašnju petlju se u stvari vršilo pomeranje početne vrednosti koja se koristila za prolaženje kroz unutrašnju, dok je poslednja vrednost u unutrašnjoj petlji bila fiksirana. Zadatak bi mogli da obrnemo, tj. da fiksiramo početak, a da spoljašnjom petljom menjamo krajnju vrednost.
Tada bi u svakoj sledećoj iteraciji imali za 1 element više da saberemo. Npr:
Ako bi u nekoj iteraciji sabirali elemente:

{3,5,-10}

u sledećoj bi sabirali:

{3,5,-10 -34}

Možemo da zaključimo da je zbir u drugoj iteraciji zbir u prethodnoj uvećan za poslednji element:
zbirUNekojIteraciji=zbirUPrethodnojIteraciji+(-34).
Na ovaj način smo došli do Kadaneovog Algoritma za određivanje maksimalne sume uzastopnih podnizova.

​Prethodno
​|<Osnovne strukture podataka		 Sledeće
​​Osnovne strukture podataka>|
Kadaneov Algoritam