2424 - 求最大面积
时间限制 : 1 秒
内存限制 : 128 MB
HISTOGRA-Largest Rectangle in a Histogram。如图所示,在一条水平线上有n个宽为1的矩形,问里面包含的矩形的最大面积是多少(图中的阴影部分的面积即所求答案)。
输入
有多组测试数据,每组数据占一行。输入零时读入结束。
每行开头为一个数字,接下来在同一行给出n个数字h1,h2,…,hn,表示每个矩形的高度。
输出
对于每组数据,输出最大子矩阵面积,一组数据输出一行。
样例
输入复制
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
输出复制
8 4000