题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N],l[N],r[N],q[N];
int main()
{
int n;
while(scanf("%d",&n),n)
{
for(int i = 1;i <= n; i++)cin >> h[i];
long long res = 0;
int tt = 0;
q[0] = 0;
for(int i = 1; i <= n; i ++)
{
while(tt && h[q[tt]] >= h[i])tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
for(int i = n;i; i --)
{
while(tt && h[q[tt]] >= h[i])tt--;
r[i] = q[tt];
q[++tt] = i;
}
for(int i = 1; i <=n ;i ++)
{
res = max(res,(long long)h[i] * (r[i] - l[i] - 1));
}
cout << res << endl;
}
return 0;
}