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 Poetakodu
def check(histogram, place, delta):
i = True
a = histogram[place]
x = place + delta
wynik = 0
while(i and x >= 0 and x < len(histogram)):
if histogram[x] < a:
i = False
break
wynik += 1
x += delta
return wynik
def check_all(histogram, place):
if histogram[place] == 0:
return 0
a = check(histogram, place, -1)
b = check(histogram, place, 1)
return histogram[place] * (a + b + 1)
def largest_rectangle(histogram):
max_val = -1
for i in range(len(histogram)):
val = check_all(histogram, i)
max_val = max(max_val,val)
return max_val
def largest_histogram(histogram):
return largest_rectangle(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!")
Nov. 19, 2016
