单调栈

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int N=1e5+10;
ll a[N];
ll Stack[N],width[N];
//单调栈，栈中的元素单调，递增或者递减，如果当前加入的元素不能满足原来的单调序列，以递增为例，小于它的栈中的元素都要出栈
//每一次出栈，都要更新一下res，同时需要更新下一个元素的宽度的贡献
//hdu1506
int main()
{
    while(~scanf("%d",&n)&&n){
        memset(Stack,0,sizeof(Stack));
        memset(width,0,sizeof(width));
        for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        a[n]=0;
        int top=0;
        ll res=0;
        for(int i=0;i<=n;i++){
            if(a[i]>Stack[top]){
                Stack[++top]=a[i];
                width[top]=1;
            }
            else{
                int widthsum=0;
                while(Stack[top]>a[i]&&top>0){
                    widthsum+=width[top];
                    res=max(res,1LL*widthsum*Stack[top]);
                    top--;
                }
                Stack[++top]=a[i];
                width[top]=widthsum+1;
            }
        }
        printf("%lld\n",res);
    }
    return 0;