Hello, i'm an OI contestant and recently I found a lot of problems like this one:
You have a n by n matrix, each cell is either 0 or 1. Find the maximum subsquare in which all the cells are 1.
This is the classic problem, but there are a lot of variants: find the maximum rectangle, find the maximum area of two consecutive subsquares, etc.
I know a solution in O(n^3) and I know there is a solution in O(n^2) but I can't understand it, can you please explain me how it works? or give me some resource to read about it?
Also I have a particular interest in "find the maximum area of two consecutive subsquares".
It'd be great if you can help me, thanks!
Let dp(i,j) be: The largest square sub matrix length with bottom right corner as cell (i,j).
No Try finding the link between dp(i,j) and dp(i-1,j-1) in O(1).
Yeah, i found the link :D Thanks.
this problem can be reduced to this http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html, check the explanation here http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
for the problem of the matrix you can fix a row and run the algorithm above in a new array of size # of columns, where the entry in position i is equal to the maximum sequence of one in column i above the (r, i) entry, here r is the current row...
Thanks!
Hi Maxi! I know you understand the problem now, but anyways here's a very good video for those who want to learn how to solve it.
https://www.youtube.com/watch?v=g8bSdXCG-lA&feature=youtu.be
It's the cuadratic solution.