This is the maximal rectangle problem: http://www.drdobbs.com/184410529 In particular, the last solution provided in the article is the application of the solution of another interesting problem: Largest rectangle in a Histogram (problem H in the following link). http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html Both of them have many solutions that are of different complexity.
【在 b********h 的大作中提到】 : This is the maximal rectangle problem: : http://www.drdobbs.com/184410529 : In particular, the last solution provided in the article is the application : of the solution of another interesting problem: Largest rectangle in a : Histogram (problem H in the following link). : http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html : Both of them have many solutions that are of different complexity.
True. I misread the problem. I think the correct solution is DP with the following recurrence: S[i][j] = min{ S[i-1][j], S[i][j-1], S[i-1][j-1] } + 1, where S[i][j] is the maximal size of the square with its bottom right at (i,j) and (i,j) contains the value you are looking for (either 0 or 1). The largest S[i][j] is the answer .
【在 b********h 的大作中提到】 : True. I misread the problem. I think the correct solution is DP with the : following recurrence: : S[i][j] = min{ S[i-1][j], S[i][j-1], S[i-1][j-1] } + 1, where S[i][j] is the maximal : size of the square with its bottom right at (i,j) and (i,j) contains the : value you are looking for (either 0 or 1). The largest S[i][j] is the answer : .