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 marcelina.gorzelana
def largest_histogram(hist):
cur = 0
rec = 0
if len(hist) == 1:
rec = hist[0]
else:
for i in range(max(hist)):
j = 0
while j < len(hist) - 1:
cur = 0
while hist[j] >= i + 1 and j < len(hist) - 1:
cur+= (i+1)
j+= 1
if hist[j] >= i + 1:
cur+= (i+1)
if cur > rec:
rec = cur
if j < len(hist) - 1:
j+= 1
return rec
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!")
Nov. 22, 2016
