def largestRectangleArea_complex(self, height):
        """
        O(n*n) + prune

        starting from every column, scan backward to calculate the max possible area under current column

        reference: http://fisherlei.blogspot.sg/2012/12/leetcode-largest-rectangle-in-histogram.html
        :param height: a list of int
        :return: int
        """
        if not height:
            return 0

        global_max = -1<<32
        for ind, val in enumerate(height):
            if ind+1<len(height) and val<=height[ind+1]:  # PRUNE, find until peak
                continue

            min_h = val
            global_max = max(global_max, min_h*1)
            for j in xrange(ind, -1, -1):  # scanning backward
                min_h = min(min_h, height[j])
                current_area = min_h*(ind-j+1)
                global_max = max(global_max, current_area)

        return global_max
dataset/ETHPy150Open algorhythms/LeetCode/082 Largest Rectangle in Histogram.py/Solution.largestRectangleArea_complex/original