最大矩形面积

Grade 100 Open Time Thursday, 4 June 2020, 7:35 AM
Discount 0.8 Time Discount Thursday, 4 June 2020, 7:35 AM
Allow late Yes Close Time Thursday, 4 June 2020, 7:35 AM
Input file rectangle.in Output file rectangle.out

【题目描述】最大矩形面积(rectangle) POJ 2559

如图2.9所示,给定从左到右多个矩形,已知矩形的宽度都为1,长度不完全相等。这些矩形相连排成一排,求在这些矩形包括的范围内能得到的面积最大的矩形。

所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。

图2.9

 

【输入格式】

输入包含多组数组,每组数据有一个整数n(1≤n≤100 000),表示矩阵数量,接下来n个数h1,…,hn,(0≤hi≤1 000 000 000),表示从左到右的矩阵高度,所有数据结束以0表示。

【输出格式】

每一组数据输出最大矩形面积。

【输入样例】

7 2 1 4 5 1 3 3

4 1000 1000 1000 1000

0

【输出样例】

8

4000