10.62 Let A be an N-by-N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square. a. Design an O(N2) algorithm that determines the size of the largest submatrix of ones in A. For instance, in the matrix that follows, the largest submatrix is a 4-by-4 square. 10111000 00010100 00111000 00111010 00111111 01011110 01011110 00011110 b. Repeat part ( a) if S is allowed to be a rectangle instead of a square. Largest is measured by area. | |
| View Solution | |
| << Back | Next >> |