Maximal Rectangle : O(n^2)

the time complexity is O(n^2), the space complexity is O(n^2)