Square04102019

 This problem was asked by Square.

You are given a histogram consisting of rectangles of different heights. These heights are represented in an input list, such that [1, 3, 2, 5] corresponds to the following diagram:

      x
      x  
  x   x
  x x x
x x x x

Determine the area of the largest rectangle that can be formed only from the bars of the histogram. 
For the diagram above, for example, this would be six, representing the 2 x 3 area at the bottom right.

'''Solution Charles''' ( solution en moyenne en nln(n)

def min_and_index(l):
  if not l:
   raise("Empty list")
  m, i = l[0], 0
  for k in range(len(l)):
   if l[k]<m:
    m, i = l[k], k
  return (m, i)

def get_area_max(l):
 n = len(l)
 if n == 0:
  return -1
 if n == 1:
  return l[0]
 else:
  (m, k) = min_and_index(l)
 return max(get_area_max(l[:k]), n*m, get_area_max(l[(k+1):]))