i**9
发帖数: 351 | 1 一道老题，求最大square 可以用 DP
http://geeksforgeeks.org/?p=6257
Let the given binary matrix be M[R][C]. The idea of the algorithm is to
construct an auxiliary size matrix S[][] in which each entry S[i][j]
represents size of the square sub-matrix with all 1s including M[i][j] and
M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
求最大的rectangle有什么解法？ | i**********e
发帖数: 1145 | 2 See the maximal rectangle solution explained here using step-wise
improvement:
http://www.drdobbs.com/184410529
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module (search for maximal rectangle)
The optimal solution is O(M*N) (ie, the size of the rectangle). This problem
is actually very much related to this problem "Largest Rectangle in a
Histogram", which can be solved efficiently in O(N) time.
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm
Basically, the easiest way to solve this is using a stack to exploit the
special structure.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**9
发帖数: 351 | 3 Thanks!
(search for maximal rectangle)
problem
【在 i**********e 的大作中提到】
: See the maximal rectangle solution explained here using step-wise
: improvement:
: http://www.drdobbs.com/184410529
: http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module (search for maximal rectangle)
: The optimal solution is O(M*N) (ie, the size of the rectangle). This problem
: is actually very much related to this problem "Largest Rectangle in a
: Histogram", which can be solved efficiently in O(N) time.
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm
: Basically, the easiest way to solve this is using a stack to exploit the
: special structure.
|
|
