[python][algospot] 울타리 잘라내기

구종만의 알고리즘 문제해결 책을 본 후 파이썬으로 짜봤다.

def brute_force(h):
    ret = 0
    N = len(h)
    for left in range(N):
        minHeight = h[left]
        for right in range(left, N):
            minHeight = min(minHeight, h[right])
            ret = max(minHeight*(right-left+1), ret)
    return ret

print(brute_force([7,1,5,9,6,7,3]))
print(brute_force([1,4,4,4,4,1,1]))

def divide_conquer(h):
    def solve(left, right):
        if left == right: return h[left]

        # 이 둘이 중요.
        mid = (left + right) // 2  # divide
        ret = max(solve(left, mid), solve(mid+1, right))  # divide and conquer

        lo , hi = mid, mid+1  # 중앙에 걸치는 녀석들을 잡기 위해
        height = min(h[lo], h[hi])  # 중앙에서 낮은 판자높이를 구함. (초기값)
        ret = max(ret, height*2)  # [mid,mid+1]만 포함하는 너비 2인 사각형 고려

        # 후처리작업 병합정렬처럼 반으로 잘라서 각개격파를 했지만
        # 병합정렬과는 다르지만 부족한 면을 반복문으로 메꾸는 것.
        # 사각형이 입력 전체를 덮을 때까지 확장한다.
        while (left < lo or hi < right):
            # 더 높은 판자를 향해 확장한다. (낮은 판자로 가면 최대값을 구할 수 없다.)
            if (hi < right and (lo == left or h[lo-1] < h[hi+1])):
                hi += 1
                height = min(height, h[hi])
            else:
                lo -= 1
                height = min(height, h[lo])
            ret = max(ret, height*(hi-lo+1))

        return ret
    return solve(0, len(h)-1)


print('divide_conquer')
print(divide_conquer([7,1,5,9,6,7,3]))
print(divide_conquer([1,4,4,4,4,1,1]))