KADANEOV ALGORITAM
ZA ODREĐIVANJE MAKSIMALNE SUME UZASTOPNOG PODNIZA
Za razliku od algoritma za određivanje maksimalne sume podniza prema definiciji problema koji je spor i ima kvadratnu složenost, Kadanov algoritam je brži jer je linearne složenosti.
Pretpostavimo da je dat sledeći niz celih brojeva:
{3,5,-10,-34,16 2}
određivanje maksimalne sume bi se po Kadanovom algoritmu uradilo na sledeći način:
- Prvo se učita ili zada niz, čija se maksimalna suma uzastopnih podnizova određuje. Npr. niz prethodno prikazan
- Odredi se dimenzija niza
- Kreiraju se dva maksimuma zbira: jedan koji pamti trenutni maksimum posle završetka iteracije spoljašnje petlje a drugi je maksimum od samog početka. Obe promenjljive inicijalizujemo na nulu.
- Kroz spoljašnju petlju pomeramo tekuću poziciju za elemente niza od prve do poslednje.
- Za tekuću poziciju kreiramo zbir tako što na prethodni maksimalni zbir dodamo tekući član niza.
- Uporedimo maksimum koji smo dobili kao trenutni na kraju iteracije, sa maksimalnim zbirom od početka i ako je veći, ažuriramo postojeći maksimum.
- U slučaju da za trenutni maksimum dobijemo negativan broj, što se može desiti ako je tekući element niza negativan broj, onda ga postavimo na nulu, jer uvek među podnizovima postoji prazan niz, čiji je zbir jednak nuli.
- Postupak se ponavlja sve dok se ne završi spoljašnja petlja.
#include < stdio.h >
int main()
{
int main()
{
int niz[]={ 3,5,-10,-34,16 2};
int n= sizeof(niz)/sizeof(niz[0]); //dimenzija niza
int MaxTrenutni=0; //trenutni maksimum posle završetka iteracije spoljašnje petlje
int Max=0; //maksimalni zbir od početka
/*Kroz spoljašnju petlju pomeramo tekuću poziciju za elemente niza od prve do poslednje*/
for(int tekInd=0; tekInd< n; tekInd++)
{
printf("Maksimalni zbir neprekidnog podniza je %3d", Max);
return 0;
}int n= sizeof(niz)/sizeof(niz[0]); //dimenzija niza
int MaxTrenutni=0; //trenutni maksimum posle završetka iteracije spoljašnje petlje
int Max=0; //maksimalni zbir od početka
/*Kroz spoljašnju petlju pomeramo tekuću poziciju za elemente niza od prve do poslednje*/
for(int tekInd=0; tekInd< n; tekInd++)
{
MaxTrenutni=MaxTrenutni+niz[tekInd]; //Kreiramo zbir za tekuću poziciju
if(MaxTrenutni>Max)
}if(MaxTrenutni>Max)
Max=MaxTrenutni;//ako je trenutni maksimum veći , ažuriramo postojeći maksimum
if(MaxTrenutni < 0)/*U slučaju da za trenutni maksimum dobijemo negativan broj koristimo zbir od praznog podniza, koji je 0*/
MaxTrenutni = 0;
MaxTrenutni = 0;
printf("Maksimalni zbir neprekidnog podniza je %3d", Max);
return 0;