Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Largest Rectangle in a Histogram by dominikbrandon
def largest_histogram(histogram):
mx = 0
possibilities = len(histogram)
for width in range(1, len(histogram) + 1):
start = 0
numOfRect = 1 # number of rectangles must be lower or equal number of possible rectangles
while start < len(histogram) and numOfRect <= possibilities:
minHeight = histogram[start]
step = 1 # step must be lower the width of a rectangle
while(step < width):
if histogram[start + step] < minHeight:
minHeight = histogram[start + step]
step += 1
rectangle = minHeight * width
if rectangle > mx:
mx = rectangle
numOfRect += 1
start += 1
possibilities -= 1
return mx
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert largest_histogram([5]) == 5, "one is always the biggest"
assert largest_histogram([5, 3]) == 6, "two are smallest X 2"
assert largest_histogram([1, 1, 4, 1]) == 4, "vertical"
assert largest_histogram([1, 1, 3, 1]) == 4, "horizontal"
assert largest_histogram([2, 1, 4, 5, 1, 3, 3]) == 8, "complex"
print("Done! Go check it!")
Oct. 29, 2016
