分析
毒瘤POJ,竟然不资瓷bits/stdc++.h
。
用单调栈维护一下矩形就行了。
单调栈经典应用。
要开long long。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;
const int MAXN=100000+10;
int n,ans;
int a[MAXN],w[MAXN];
int sta[MAXN],top=0;
inline void solve() {
for (re int i=1;i<=n;++i) scanf("%lld",a+i);
ans=top=0; a[n+1]=0;
for (re int i=1;i<=n+1;++i) {
if (a[i]>sta[top]) sta[++top]=a[i],w[top]=1;
else {
int width=0;
while (sta[top]>a[i]) {
width+=w[top];
ans=max(ans,width*sta[top]);
--top;
}
sta[++top]=a[i],w[top]=width+1;
}
}
printf("%lld\n",ans);
}
mainint main() {
while (scanf("%lld",&n)) {
if (!n) break;
solve();
}
return 0;
}