题目大意：
给定n个连续的长度为1的矩形的高度h（1<=n<=100000，0<=hi<=1000000000），问你其中能构成的最大矩形的面积是多少。
思路：
很显然，用DP。但关键是怎样表示状态，一开始想用一个二维数组min[][]表示从i～j的最小高度，面积就等于min[i][j]*(j-i+1)。但很不幸，根据题目给定的n的范围，这个二维数组根本无法创建。:(
后来从论坛上得到提示，因为对于图中的某个面积最大的矩形，必然有一个最低的高度h[k]，即矩形的高等于h[k]，以第k块矩形的高度，最左边可以到达这个矩形的左边，最右边可以到达这个矩形的右边。所以，可以以每块矩形进行扩展，求出最左边和最右边（即两边的高度都大于等于这块的高度），得出面积s[i]，这样就可求出最大的s[i]了。
代码：
#include <cstdio>
const int MAX = 100005;
__int64 h[MAX];
__int64 left[MAX], right[MAX]; //left[i] = j表示第i个矩形以它的高度到达最左边的下标
int n;
bool Input ()
{
scanf("%d", &n);
if ( n == 0 )
return false;
int i;
for (i=1; i<=n; i++)
scanf("%I64d", &h[i]);
h[0] = h[n+1] = -1;
return true;
}
void Solve ()
{
int i;
__int64 temp, max;
for (i=1; i<=n; i++)
{
left[i] = right[i] = i;
}
for (i=1; i<=n; i++)
{
while ( h[left[i]-1] >= h[i] )
left[i] = left[left[i]-1];
}
for (i=n; i>0; i--)
{
while ( h[right[i]+1] >= h[i] )
right[i] = right[right[i]+1];
}
max = 0;
for (i=1; i<=n; i++)
{
temp = h[i] * (right[i] - left[i] + 1);
if ( temp > max )
max = temp;
}
printf("%I64d\n", max);
}
int main ()
{
while ( Input() )
{
Solve();
}
return 0;
}