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