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
{ 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.
{}, {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:
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("/n");
}{
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("/n");
}{
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()
{
#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++)
{
printf("M=%3d",M);
}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++)
{
printf("/n");
}for(int kr=poc; kr < n; kr++)
{
z=z+niz[kr];
if(z>M)
}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.
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.
|
Sledeće
Osnovne strukture podataka >| |