Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
three solutions solution in Clear category for Largest Rectangle in a Histogram by CDG.Axel
# from itertools import combinations
def largest_histogram(histogram):
# my third solution, no intertool required
return max(min(histogram[i:j + 1]) * (j - i + 1)
for i in range(len(histogram))
for j in range(i, len(histogram)))
"""
# first solution
ln, mx = len(histogram), 0
for i in range(ln):
for j in range(i, ln):
ml = min(histogram[i:j+1])
mx = max(mx, ml * (j-i+1))
return mx
# second solution required intertools
return max([(1 + abs(x-y)) * min(histogram[x:y+1])
for x, y in combinations(range(len(histogram)), 2)], default=histogram[0])
"""
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!")
Sept. 3, 2021
