#include <cstdio>
int main(void)
{
    __int64 h[100005],ans;
    int left[100005],stack[100005],id[100005],top,i,j,n;//如果开了两个
//left和right的话,会爆了,所以只开一个,另个加上去
    while (scanf("%d",&n)&&n)
    {
        h[0]=h[n+1]=-1;//方便退栈
        for ( i=1,ans=-1; i<=n; i++)
            scanf("%I64d",&h[i]);
        for ( i=2,stack[top=0]=h[1],id[top]=1; i<=n+1; i++)
        {
            j=top;
            while (top>=0&&h[i]<stack[top])//退栈
            {
                left[id[top]]=j-top;
                top--;
            }
            stack[++top]=h[i];
            id[top]=i;
        }
        for ( i=n-1,stack[top=0]=h[n],id[0]=n; i>=0; i--)
        {
            j=top;
            while (top>=0&&h[i]<stack[top])
            {
                left[id[top]]+=j-top;
                top--;
            }
            stack[++top]=h[i];
            id[top]=i;
        }
        for ( i=1; i<=n; i++)
        {
            __int64 t=h[i]*(left[i]+1);
            if (ans<t)
                ans=t;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

• Re:WA了好久,好心人看看,用栈做的 (53) Dereky 2011-05-09 18:29:46