Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Backtracking solution in Clear category for Largest Rectangle in a Histogram by Krischtopp
def largest_histogram(histogram):
''' Backtracking solution
Outer loop, left end of the rectangle:
for first in range(len(histogram))
Inner loop, right end of the rectangle:
for last in range(first, len(histogram))
Calculate current rectangle:
height * width
min(histogram[first:last+1]) * (last - first + 1)
max() to find the biggest rectangle '''
return max(min(histogram[first:last+1]) * (last - first + 1)
for first in range(len(histogram))
for last in range(first, len(histogram)))
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!")
Feb. 2, 2020
