#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int h[N], q[N];
int l[N], r[N];//左(右)边高度>=自己的个数(包括自己)
int main()
{
int n;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
h[0] = h[n + 1] = -1;
int tt = -1;
q[++ tt] = 0;
for(int i = 1; i <= n; i++ )
{
while(h[q[tt]] >= h[i]) tt --;
l[i] = i - q[tt];
q[++ tt] = i;
}
tt = -1;
q[++ tt] = n + 1;
for(int i = n; i >= 1; i -- )
{
while(h[q[tt]] >= h[i]) tt --;
r[i] = q[tt] - i;
q[++ tt] = i;
}
ll res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, (ll) h[i] * (l[i] + r[i] - 1));
cout << res << endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla