Try using stack to solve in O(n^2)


#1

convert the problem in such a way that each row becomes an array of histogram in which you have to find the maximum are of rectangle.