Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Largest Rectangle in a Histogram solution in Speedy category for Largest Rectangle in a Histogram by Tavisevik
def largest_histogram(histogram):
n = len(histogram)
maxs = histogram[0]
for i in range(n):
minh = histogram[i]
for j in range(i+1, n):
if histogram[j] < minh:
minh = histogram[j]
s = minh * (j-i+1)
if maxs < s:
maxs = s
return maxs
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!")
Dec. 10, 2020
Comments:
