利用单调栈算法，找到每一个数左侧和右侧第一个小于自己的数，则两个数间隔的长度乘以当前数的高度即为一个备选答案。从所有答案中选择最大值即可，时间复杂度 $O(n)$。

关于单调栈的内容，可以自行在网上搜索。以下给出一个模板。

#include <stdio.h>
#include <vector>
#include <algorithm>
typedef long long i64;
// 1-indexed
template <typename T, typename F>
struct nearest_bound
{
    int n;
    std::vector<T>& a;
    std::vector<int> pre, suf;
    F f;
    bool op(int x, int y) { return f(a[x], a[y]); }
    // pre[i] = 0 or suf[i] = 0 means pre/suf nearest bound do not exist.
    nearest_bound(F _f, std::vector<T>& _a) : f(_f), n(_a.size() - 1), a(_a), pre(_a.size(), 0), suf(_a.size(), _a.size())
    {
        std::vector<int> s;
        for (int i = 1; i <= n; ++i)
        {
            while (s.size() && !op(s.back(), i)) s.pop_back();
            if (s.size()) pre[i] = s.back();
            s.push_back(i);
        }
        s.clear();
        for (int i = n; i; --i)
        {
            while (s.size() && !op(s.back(), i)) s.pop_back();
            if (s.size()) suf[i] = s.back();
            s.push_back(i);            
        }
    }
};
int n;
int main()
{
    auto f = [](int a, int b) { return a < b; };
    scanf("%d", &n);
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    nearest_bound<int, decltype(f)> near_lower_bound(f, a);
    i64 ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int tmp_l = near_lower_bound.pre[i] + 1, tmp_r = near_lower_bound.suf[i] - 1;
        ans = std::max(ans, 1ll * (tmp_r - (tmp_l - 1)) * a[i]);
    }
    printf("%lld", ans);
}