***** Pojasnjenje algoritama za problem Matrica ******

Tekst problema je poznat - dakle necu ga navoditi. Posluzicu se primerom
navedenim u postavci. Dakle polazna matrica je:
  1   1   1   0 -50
  1  -9   1   0   0
  1   2   1   1   1
  0   0   1   8   1
-50   0   1   1   1

Kao prvo sta i kako radi funkcija ComputeSum:
Posto nam se trazi podmatrica sa maksimalnom sumom, za pocetak
ne bi bilo lose da imamo bilo kakvu medju sumu sa kojom bi lakse radili.
Inace princip dinamickog programiranja moze da glasi: resavamo prvo
manji problem, da bi smo lakse resili veci (iako nam mali ne treba :)

Funkcija ComputeSum pravi novu matricu (koja se, ako treba pristedeti
memoriju moze pisati preko postojece - jer nam ova kasnije ne treba)
cije clanove mozemo opisati na sledeci nacin:
Clan S(i, j) jednak je zviru elemenata podmatrice sa koordinatama
(1, 1, i, j). Dakle logicno: S(1, 1, 1, 1) je prvi element matrice,
S(1, 1, n, n) je zbir svih clanova matrice. Na ovaj nacin od gore napisane
matrice, dobijamo neso ovako:
  1   2   3   3 -47
  2  -6  -4  -4 -54
  3  -3   0   1 -48
  3  -3   1  10 -38
-47 -53 -48 -38 -85

Za racunanje clanova ovakve matrice potrebna je slozenost n^2 (moramo da
izracunamo n^2 elemenata). Racunanje vrsimo po vrstama (moze i po kolonama),
krecuci od prvog clana, stim sto najpre moramo da izracunamo 1. vrstu i 1.
kolonu (mozemo i bez ovog, ali to cu napomenuti malo kasnije).
Oznacimo polaznu matricu sa A, a matricu suma sa S.
Element S(i, j) racunamo:
	S(i, j)=S(i-1, j) + S(i, j-1) - S(i-1, j-1) + A(i, j)
ovo se moze izvesti iz principa ukljucenja-iskljucenja, ili kako sam pomenuo
u obrisanoj poruci - zdravog razuma :)
Kao sto se primecuje potrebni su nam vec izracunati elementi prethodne vrste
i prethodne kolone, zbog cega sam gore napomenuo da na pocetku treba prvo njih
izracunati. Ukoliko ipak ne racunate njih na pocetku, potrebno je kasnije, u
toku izracunavanja proveriti indekse ((i, j) - za slucaj (1, 1)), odnosno
elemente koji ne postoje smatrati nulama.
Ono sto je dobro u ovoj funkciji jeste da se suma elemenata neke podmatrice
(1, 1, i, j) ne racuna, sabiranjem svih vec jednim izrazom sto celoj funkciji
daje slozenost O(n^2).


*** ALGORITAM I :

U ovom algoritmu je prikazano jednostavno koriscenje matrice S. Uocimo da za
bilo koju podmatricu (i1, j1, i2, j2) sumu njenih elemenata mozemo izracunati
na sledeci nacin:

Suma=S(i2, j2) - S(i1-1, j2) - S(i2, j1-1) + S(x1-1, j1-1)
	- uz napomenu da i ovde treba proveriti indekse
	- ovaj izraz se takodje dobija primenom principa ukljucenja-iskljucenja
Dakle za svaku mogucu podmatricu (i1, j1, i2, j2) izracunamo sumu navedenim izrazom
i odaberemo najmanju, sto daje slozenost O(n^4).


*** ALGORITAM II :

Nije tesko zapaziti da nam elementi matrice S pruzaju neku vrstu redukcije po
poslednjoj vrsti, odnosno koloni. Da pojasnim, nama svaki element (i, j) matrice
S moze predstavljati sumu u podmatrici koja se zavrsava u (i, j), samo je potrebno
izvrsiti jos i odgovarajucu redukciju u odnosu na 1. vrstu i 1. kolonu podmatrice.
Primer:
Uocimo S(5, 4) = -38. Mozemo smatrati da nam je ovo poslednji element podmatrice,
tj. da su njene koordinate (x, y, 5, 4). Nama je potrebno da nadjemo neki pametniji
nacin da odaberemo x i y, da bi smo dobili najvecu sumu. Pri tom, znamo da treba
odbaciti elemente cija je vrsta manja od x (kolona <= 4) i elemente cija je kolona
manja od y (vrsta <= 5). Logicno x i y treba odabrati tako da je suma tih elemenata
sto manja (i negativna) jer cemo jedino tako povecati sumu u odnosu na podmatricu
(1, 1, 5, 4). Ideja je sledeca:
1. Nadjemo najmanji element u 4. koloni "iznad" elementa (5, 4) - tj. cija je vrsta
 manja od 5. Posto tu pravimo rez sve elemente u matrici S koji se nalaze 5. vrsti,
 a kolona im je < 4 mozemo da umanjimo za sume koje "rezemo". Dakle posto smo nasli
 element S(2, 4) = -4, umanjujemo ih za vrednosti iz 2. vrste (do 4. kolone). Sada
 nam 5. vrsta izgleda ovako: -49 -47 -44 -34 -85. Nadjemo najmanju sumu po koloni
 (a ona se nalazi u 5. vrsti "levo" od (5, 4) - tj. kolona < 4 - u ovom slucaju to
 je -49 = S(5, 1)) i tu pravimo rez. Dakle suma koju smo dobili je -34-(-49)=15.
 Ta suma je JEDAN od najverovatnijih kandidata za maksimalnu sumu.
 Vazno je napomenuti 2 stvari: prvo, ukoliko ne nadjemo negativan element ne treba
 rezati nista jer time mozemo samo pokvariti sumu tj. smanjiti je; drugo, ako u
 pretrazi elemenata u koloni iznad odgovarajuce vrste (dakle, ovo prvo pretrazivanje)
 nadjemo vise jednakih elemenata koji su negativni i najmanji, potrebno je ZA SVAKI
 od njih posebno ponoviti objasnjeno oduzimanje od vrste i proveru !
2. Osim minimuma u koloni i minimalni element u vrsti takodje predstavlja kandidata
 za popravljanje sume. Istu stvar treba ponoviti (kao sto je opisano pod 1.) stim
 sto sada najmanje elemente uzimamo iz vrste levo od (5, 4) a oduzimanje vrsimo
 od 4. kolone pa ce pronalazenje broja -53 dati izgled 4. koloni ovako:
 1 2 4 13 15. Obzirom da nema negativnih za najvecu sumu u ovom slucaju dobijamo 15.

Sto se tice korektnosti algoritma mislim da sam uspeo da dokazem da nije heuristika.
Dokaz necu sada iznositi ali se zasniva na tome da svako umanjenje neke negativne
sume koja nije minimalna povlaci unakrasno umanjenje odredjene sume (vrste-kolone),
a zbir elemenata ostaje konstantan u delu na koji umanjenje nema uticaja. Slucaj
za pozitivne brojeve je trivijalan. Jos, jednom moguce je da gresim ali stvarno
me mrzi da kucam kompletnu analizu mogucih situacija a trebalo bi da je OK.

Slozenost ovog algoritma je O(n^3) - sto bi za n=60 trebalo da se izvrsi manje-vise
trenutno. Analiza koju sam pomenuo za najgori slucaj (tzv. Worst Case) bi bila
priblizno O(n^4) - ako je veliki broj minimalnih elemenata koje sam gore pominjao.
Uzmimo za primer matricu ciji je element A(1, 1) = -1, a svi ostali su nule. Tada ce
svi elementi matrice S biti jednaki -1. Ipak takvih slucajeva nema bas mnogo....


****** GENERALNE NAPOMENE ******
1. Oba algoritma su jednako vazeca i da matrica nije kvadratna - u implementaciji
  treba samo uvesti oznaku druge dimenzije i usaglasiti kretanje brojaca.
2. Da se uociti da se od matrice suma (S) moze rekonstruisati polazna matrica, ako
  bude potrebno - tako sto racunamo element, po element po izrazu:
  A(i, j) = S(i, j) - S(i-1, j) - S(i, j-1) + S(i-1, j-1)
  Ukoliko se radi rekonstrukcija "u mestu", tj. u matrici S, onda krecemo od (n, n).
3. Matrica S se ne mora nuzno praviti polazeci iz gornjeg levog ugla (1, 1) vec iz
  bilo kog, s tim sto se znacenje elemenata matrice S tada menja i potrebno je
  adekvatno izmeniti algoritam (sve se onda gleda u odnosu na taj ugao).
********************************
Toliko od mene o ovom problemu. Ukoliko mi neka sjajna ideja padne na pamet (mislim
na bolje resenje), javicu, ali ne planiram bas da se posvetim ovom problemu....
Posto me mrzi da citam ovaj tekst, ne zamerite na greskama u kucanju ako ih ima...

U zdravlje, Nine !