POJ 2559

题意略。

思路：

从中间开始向两边搜索，寻求第一个比当前元素大/小的元素的位置，可用单调栈来维护。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn = 100005;

struct node{
    LL h,idx;
    node(LL a = 0,LL b = 0){
        h = a,idx = b;
    }
};

node stk[maxn];
int tp;
LL store[maxn],l[maxn],r[maxn];

int main(){
    int n;
    while(scanf("%d",&n) == 1 && n){
        LL ans = 0;
        tp = 0;
        for(int i = 0;i < n;++i){
            scanf("%lld",&store[i]);
        }
        for(int i = 0;i < n;++i){
            while(tp && stk[tp - 1].h >= store[i]){
                --tp;
            }
            l[i] = tp == 0 ? -1 : stk[tp - 1].idx;
            stk[tp++] = node(store[i],i);
        }
        tp = 0;
        for(int i = n - 1;i >= 0;--i){
            while(tp && stk[tp - 1].h >= store[i]){
                --tp;
            }
            r[i] = tp == 0 ? n : stk[tp - 1].idx;
            stk[tp++] = node(store[i],i);
        }
        for(int i = 0;i < n;++i){
            ans = max(ans,(r[i] - l[i] - 1) * store[i]);
        }
        printf("%lld
",ans);
    }
    return 0;
}