題目大意：
給定n個(gè)連續(xù)的長度為1的矩形的高度h（1<=n<=100000，0<=hi<=1000000000），問你其中能構(gòu)成的最大矩形的面積是多少。
思路：
很顯然，用DP。但關(guān)鍵是怎樣表示狀態(tài)，一開始想用一個(gè)二維數(shù)組min[][]表示從i～j的最小高度，面積就等于min[i][j]*(j-i+1)。但很不幸，根據(jù)題目給定的n的范圍，這個(gè)二維數(shù)組根本無法創(chuàng)建。:(
后來從論壇上得到提示，因?yàn)閷?duì)于圖中的某個(gè)面積最大的矩形，必然有一個(gè)最低的高度h[k]，即矩形的高等于h[k]，以第k塊矩形的高度，最左邊可以到達(dá)這個(gè)矩形的左邊，最右邊可以到達(dá)這個(gè)矩形的右邊。所以，可以以每塊矩形進(jìn)行擴(kuò)展，求出最左邊和最右邊（即兩邊的高度都大于等于這塊的高度），得出面積s[i]，這樣就可求出最大的s[i]了。
代碼：
#include <cstdio>
const int MAX = 100005;
__int64 h[MAX];
__int64 left[MAX], right[MAX]; //left[i] = j表示第i個(gè)矩形以它的高度到達(dá)最左邊的下標(biāo)
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;
}