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 masa02ish
def largest_histogram(histogram):
if len(histogram) == 1:
return histogram[0]
possible = divided(histogram)
rectangles = [len(rectangle) * min(rectangle) for rectangle in possible]
rectangles.append(len(histogram))
return max(rectangles)
def divided(histogram):
possible = []
temporary = []
for i in histogram:
if i != 1:
temporary.append(i)
else:
possible.append(temporary)
temporary = []
possible.append(temporary)
possible = [list for list in possible if list != []]
return possible
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. 30, 2016
