Kaj fali ovome:
max = 0
za svaki podniz:
1) izračunaj sumu
2) vidi je li veća od max i promijeni max ako je
ispisi_max
Kaj fali ovome:
max = 0
za svaki podniz:
1) izračunaj sumu
2) vidi je li veća od max i promijeni max ako je
ispisi_max
Postoji 2n podnizova, pa bi to bilo dosta sporo :D
Nekako logično bi mi bilo da će podniz sa najvećom sumom biti podniz koji se sastoji od samo pozitivnih (nenegativnih) članova niza. Oni negativni će sumu samo moć smanjit.
Ako pak pozitivnih nema, onda maximalnu sumu ima jednočlan niz koji se sastoji od maximalnog elementa niza.
Ako se traži u nizu od n brojeva naći niz duljine k (k fixan) sa najvećom sumom, onda je to već malo teže i trebalo bi se ispitat dosta kombinacija.
Ako umeš sve pozitivne u sumu, negativni će samo umanjit.
I kod tvog primjera suma sa malim negativnim+veliki pozitivni je opet manja od suma bez malog negativnog+veliki pozitivni.
Podniz ne mora sadržavati samo one elemente koju su susjedni u nizu. Generalno, podniz se dobije iz polaznog niza preskakanjem članova, tako da, ukoliko nema dodatnih ograničenja, podniz sastavljen samo od pozitivnih članova je točno rješenje.
E pa to je druga pjesma :D
Imam ideju kak to napravit, al je pitanje kak ću ja sad to objasnit :D Fali mi da ne vidiš moje mahanje rukama :D
Znači krećemo od sume cijelog niza, i s njom inicijaliziramo maximalnu sumu.
Radimo petlju po svim mogučim počecima podniza (petlja po i)
Zatim u petlji (po j) režemo krajnji element. Trenutna suma će bit lagana za izračunat je samo trebamo oduzet član niza koji smo odsjekli. To će biti suma podniza od niz[i] do niz[j].
Zatim odrežemo prvi element, opet je sumu od koje krećemo lako izračunat (cijela suma-niz[i])
I to provrtimo za sve.
Primjer kako bi se to vrtilo (di je novi red tu je rezanje prvog, inače je rezanje zadnjeg):
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1
2 3 4 5
2 3 4
2 3
2
3 4 5
3 4
3
4 5
4
5
Treba primjetiti da smetaju samo negativni brojevi, inace je rjesenje cijeli niz.
Postoji nekoliko algoritama.
DP - dinamicko programiranje, koje moze ovaj problem rjesiti u O( N )
Dp solucija radi na ovaj nacin.
Loopamo po nizu i rjesavamo :
dp[ i ] = max( A[ i ], dp[ i- 1 ] + A[i] ); // Jeli bolje uzeti prosli i "i-ti" ili je bolje uzeti samo "i-ti".
dakle ukoliko imamo niz :
Ar[] : 4 -2 3 -1 5
Dp[] :4 2 5 4 9
rjesenje je uzeti cijeli niz i dobiti 9
Ar[] : 4 -5 2 1 -6 5
Dp[] :4 -1 2 3 -3 5
rjesenje je uzeti samo zadnji element i imati sumu 5.
Ar[] : -5 1 3 -3 4 -6 3 1 -2 2
dp[] : -5 1 4 1 5 -1 3 4 2 4
rjesenje je uzeti [ 2, 4 ] element i imati sumu 5.
Dp solucija moze imati prostornu slozenost O( 1 ) i vremensku O( N ) gdje je N duljina niza.
Nadam se da ovo pomaze.
Smijem li pitati gdje si nasao ovaj zadatak ?
Mioc - zatemas
