算法1
(暴力枚举) $O(n^2)$
先固定 $l$,然后随着 $r$ 每次加 $1$ 来更新 $x$。
注:$\frac{n^2}{2} = 1e7$ 可以过。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::max;
using std::min;
#define rep(i, n) for (int i = 0; i < (n); ++i)
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int ans = 0;
rep(l, n) {
int x = a[l];
for (int r = l; r < n; ++r) {
x = min(x, a[r]);
ans = max(ans, x * (r - l + 1));
}
}
cout << ans << '\n';
return 0;
}
算法2
(单调栈) $O(n)$
具体做法和 柱状图中最大的矩形 这题一样。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::stack;
using std::pair;
using std::max;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)
vector<int> getLeft(vector<int> a) {
int n = a.size();
vector<int> res(n);
stack<P> ps;
ps.emplace(0, -1);
rep(i, n) {
while (ps.top().first >= a[i]) ps.pop();
res[i] = ps.top().second;
ps.emplace(a[i], i);
}
return res;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<vector<int>> d;
rep(di, 2) {
d.push_back(getLeft(a));
reverse(a.begin(), a.end());
}
vector<int> ls = d[0];
vector<int> rs = d[1];
reverse(rs.begin(), rs.end());
rep(i, n) rs[i] = n - 1 - rs[i];
int ans = 0;
rep(i, n) {
int now = a[i] * (rs[i] - ls[i] - 1);
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}