解法1 暴力 $O(n^2)$
对于每个点向左右两边扩展直到高度小于这个点 取max即可
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; scanf("%d", &n);
vector<int> a(n);
int ans = 0;
for(int &x: a) cin >> x;
for(int i = 0; i < n; i ++ ) {
int l = i, r = i;
while(l > -1 && a[l] >= a[i]) l --;
while(r < n && a[r] >= a[i]) r ++;
r --, l ++;
ans = max(ans, (r - l + 1) * a[i]);
}
cout << ans << endl;
}
解法2 单调栈维护 复杂度 $O(n)$
使用单调栈预处理出左边比它矮的和右边比它矮的第一个即可
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n, ans;
int a[N], q1[N], q2[N], stk[N];
int get(int q[]) {
int tt = 0;
for(int i = 1; i <= n; i ++ ) {
while(tt && a[stk[tt]] >= a[i]) tt --;
q[i] = stk[tt];
stk[++ tt] = i;
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
get(q1);
reverse(a + 1, a + n + 1);
get(q2);
reverse(a + 1, a + n + 1);
for(int i = 1, j = n; i <= n; i ++, j --) {
ans = max(ans, a[i] * (n + 1 - q2[j] - q1[i] - 1));
}
cout << ans << endl;
}