题目中叫求一个最大的区域，则第i个矩形对应的面积是ave[i] = (r[i] – l[i] + 1) * a[i];l[i]表示以它这个高度所能到达的最左边的位置（最左一个高度不小于它的高度的位置），而r[i]表示能到达的最右边的位置（最右一个高度不小于它的高度的位置）。
那么这个题目就转到怎么求r[]和l[]上了。如果每次依次向左向右找，肯定会超时的。这时就会用到迭代了，比如说求a[i]的l[i]，如果a[i]大于a[i-1]那么l[i] = i；如果a[i]小于a[i-1]，那么l[i]肯定小于l[i-1]，找l[i]就可以直接跳到l[i-1]的位置上。
1: #include <iostream>
2: #include <cstdio>
3: #include <cstring>
4: #include <cmath>
5: #include <algorithm>
6: using namespace std;
7: typedef long long ll;
8: const int N=100010;
9: int l[N],r[N],a[N],n;
10:
11: int main()
12: {
13: // freopen("in.txt","r",stdin);
14: while(scanf("%d",&n)>0&&n)
15: {
16: for(int i=1; i<=n; i++)
17: {
18: scanf("%d",&a[i]);
19: l[i]=r[i]=i;
20: }
21: a[0]=a[n+1]=-1;
22: for(int i=1; i<=n; i++)
23: {
24: while(a[i]<=a[l[i]-1])
25: l[i]=l[l[i]-1];
26: }
27: for(int i=n; i>0; i--)
28: {
29: while(a[i]<=a[r[i]+1])
30: r[i]=r[r[i]+1];
31: }
32: ll ans=0;
33: for(int i=1; i<=n; i++)
34: {
35: ll m=(ll)a[i]*(r[i]-l[i]+1);
36: ans=max(m,ans);
37: }
38: printf("%I64d\n",ans);
39: }
40: return 0;
41: }