Electric Station 問題 Largest rectangular

今回も説明が難しいですが、一番大きな長方形の面積を返す問題。

1. iterableにリストの数字を前から選ぶ (num)
2. 選択された数字より大きな数字が右に何個連続しているか調べる (a)
3. 反対方向にも調べる。(b)
4. num*( a - b + 1)が面積

という方向性で考えました。
まずは覚えたてのRecursionを使って、

def largest_histogram(test):
    N = len(test)
    def index(x, dir, num):
        if 0<=x+dir< N and num <= test[x+dir]:
            return dir + index(x+dir, dir, num)
        else:
            return 0
    loc_val = []
    for i in range(N):
        start = index(i, -1, test[i])
        stop  = index(i,  1, test[i])
        loc_val.append( test[i]*(stop - start + 1)   )
    return max(loc_val)

でも、これ同じoperator (test[i])が何度も出てくるのであんまり効率が良くないなぁ。 Brute forceでやる場合は、前から順番にあらゆる組み合わせで数字を切っていって、その中で

• 一番小さい数字＊長さ

でやるやり方。シンプルに下記のように書けますが、O(C^N)なので、時間はかかりますね。

def largest_histogram(test):
    return max([min(test[i:j])*(j-i) for i in range(len(test)) for j in range(i+1, len(test)+1)])