题意
一个围挡由n个宽度为1的长方形挡板下端对齐后得到，每个长方形挡板的高度为hi。我们把其抽象成一个图形，问这个图形中包含的面积最大的长方形是多大？
输入
多行数据，每行第一个为n，后面n个数，代表hi
以0为结束
输出
每行一个数
样例输入
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
样例输出
8
4000
分析
我们定一个中心为i，矩形高度为Hi，设他能在一个区间[l,r]中存在，必满足j∈[l,r]使Hj≥Hi。如果Hl-1≥Hi，显然可以继续向右扩张，那么Hl-1一定小于Hi，所以l-1是[1,i]中最后一个小于Hi的。那我们从左向右扫维护所有比Hi小的标号，形成一个单调递增的栈，栈顶即是他的左边界。同理维护右边界。
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
#define maxn 100005
using namespace std;
int n;
ll num[maxn],L[maxn],R[maxn];
struct D{
int h,id;
};
stack<D> stk;
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} void work()
{
int id;
while(!stk.empty()) stk.pop();
rep(i,,n)
{
while(!stk.empty()&&stk.top().h>=num[i]) stk.pop();
if(!stk.empty()) id=stk.top().id;
else id=;
L[i]=id+;
stk.push((D){num[i],i});
}
while(!stk.empty()) stk.pop();
per(i,n,)
{
while(!stk.empty()&&stk.top().h>=num[i]) stk.pop();
if(!stk.empty()) id=stk.top().id;
else id=n+;
R[i]=id-;
stk.push((D){num[i],i});
}
ll ans=;
rep(i,,n) ans=max(ans,num[i]*(R[i]-L[i]+));
printf("%lld\n",ans);
} int main()
{
//freopen("a","r",stdin);
while()
{
n=read();if(!n) return ;
rep(i,,n) num[i]=read();
work();
}
return ;
}