Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-04-25 07:29:52.
Revizia anterioară   Revizia următoare  

Jmenoasa

Vom transforma matricea initiala astfel:

  • Introducem intre oricare doua elemente adiacente pe orizontala un 0 daca elementul din stanga este mai mic, un 1 in caz contrar.
  • Introducem intre oricare doua elemente adiacente pe verticala un 0 daca elementul de sus este mai mic, un 1 in caz contrar.
  • Elementele initiale ale matricei se tranforma in 0.
  • Completam restul matricei cu 0.

Am redus problema la determinarea celei mai mari submatrice care incepe si se termina pe o coloana impara si cotine numai 0 pentru o matrice avand elementele in multimea {0, 1}. Putem gasi solutia adaptand cunoscutul algoritm de determinare a submatricei de 0 avand aria maxima.