柱状图中的最大矩形面积

原文地址：https://www.jianshu.com/p/7966a1ce47fc

问题描述

将一组非负整数组成的数组(h)作为柱状图中每个柱子的高度值，且每个柱子宽度为1。找出这个柱状图中所包含矩形的最大面积。

解题思路

使用分治法，最大矩形面积只可能有三种情况：

1. 取决于高度最小的柱子，此时要求的面积=最小高度*总长度；
2. 出现在高度最小的柱子的左边；
3. 出现在高度最小的柱子的右边。

程序实现

n=int(raw_input()) # 柱子数
h=[int(x) for x in raw_input().strip().split()] # 柱子高度数组
def largestArea(a):
    w=len(a)
    h_id=a.index(min(a))
    value1=w*a[h_id]
    if(h_id>0)
        value2=largestArea(a[:h_id])
    else
        value2=0
    if(h_id<len(a)-1)
        value3=largestArea(a[h_id+1:])
    else
        value3=0
    return max(value1,value2,value3)
print(largestArea(h))