Grozavesti
Observam ca daca avem la dispozitie o matrice NxN putem aduce orice element pe pozitia (1,1) in cel mult doua interschimbari (una pentru linii si una pentru coloane). Daca elementul minim se afla pe pozitia (i,j) interschimbam linia i si coloana j cu linia 1 si coloana 1. Astfel pentru fiecare x de la 1 la N vom plasa pe pozitia (x,x) cel mai mic element din submatricea avand coltul stanga sus (x,x). Acum problema se reduce la aflarea elementului minim din submatricea avand coltul stanga sus (x,x). Se poate implementa direct acest pas iterand prin toate valorile posibile si se obtine un algoritm de complexitate O(N3). Daca in loc sa ne uitam la toata submatricea, verificam doar valorile de pe diagonala principala din submatrice obtinem complexitatea O(N2), dar acest lucru nu era necesar pentru obtinerea punctajului maxim.
