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 checinski.szymon
def largest_histogram(histogram):
i = 0
j = 0
max = 0
mult = 1
while i < len(histogram):
col = histogram[i]
j = i + 1
while col > 0:
mult = 1
while j < len(histogram):
if histogram[j] >= col:
#print (str(col) + " " + str(histogram[j]))
mult += 1
else:
break
j += 1
tempRes = mult * col
if tempRes > max:
max = tempRes
col -= 1
i += 1
return max
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. 6, 2016
