Naime, data je kvadratna matrica (dvodimenzionalan niz) n x n (n kolona i n redova). Treba naći koordinate početka i kraja glavne dijagonale podmatrice (ne mora biti kvadratna) koja ima najveću sumu elemenata. Svi elementi su celi brojevi, u rasponu od -100000 do 100000, a n je manje ili jednako 60. Znači za matricu:
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
treba pronaći 3 2 5 5, jer je najveća vrednost zbira elemenata u podmatrici čija glavna dijagonala počinje u preseku 3 reda i 2 kolone (broj 2), a završava u preseku 5 reda i 5 kolone (broj 1).
U principu, u ekstremnom slučaju, da su svi elementi pozitivni, najveća podmatrica bi bila sama matrica. Kako je n veliko (max 60) samo izračunavanje svih kombinacija ne dolazi u obzir. Onda sam razmišljao da počnem od matrice označene sa 1 1 2 2 (ako uzmemo da matrica počinje sa index-om 1) pa onda izračunam matricu 1 1 2 3 i tako dalje, ali sam se pogubio kada sam uzeo da n može da bude i neparno, a opet mi se čini mnogo "prolaza".
Onda sam najviše razmišljao o ideji da iz svakog koraka u sledeći mogu na 8 različitih načina. ("smaknem" prvi red, zadnji red, prvu ili zadnju kolonu, kao i kombinacije prvi red i prva kolona, prva kolona i zadnji red, zadnji red i druga kolona, druga kolona i prvi red) Stoga mogu "probati" tih 8 vrednosti na osnovu pozicije gl. dijagonale trenutne podmatrice i odabrati najmanju, jer njenim eliminisanjem dobijam naveću preostalu vrednost. Mana toga je što ako u prvom koraku odem na 3 izbor (druga kolona) onda možda neću ni stići do neke kombinacije u kojoj sam trebao sačuvati tu treću kolonu. (ala sam ovo objasnio, ali nadam se da kapirate).
Da sortiram matricu ne mogu, jer mi trebaju koordinate.
Imate li neke ideje?
prezentacije, legalno bez troškova licenciranja