思路:

这道题需要构造一个先增后减的序列, 需要枚举每一个顶点作为「山峰」, 由于直接暴力枚举会超时, 考虑使用单调栈进行预处理。

单调栈预处理每个点k左边和右边的最大和l[k]和r[k], 则选择k作为顶点时 总和 = l[k] + r[k + 1]

/**
*   author:     roccoshi
*   created:    2021-07-24 18:55:51
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int pi = 3.1415927;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f; 
const int ninf = 0xc0c0c0c0;
const int maxn = 500000 + 5;

ll m[maxn]; // 输入
ll a[maxn]; // 答案
ll l[maxn], r[maxn]; // 单调栈预处理左右值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> m[i];
    }
    stack<int> stk; stk.push(0); m[0] = ninf; // 无穷小
    for (int i = 1; i <= n; ++i) {
        while (m[stk.top()] >= m[i]) {
            stk.pop(); 
        }
        l[i] = l[stk.top()] + (i - stk.top()) * m[i];
        stk.push(i);
    }
    while (stk.size()) stk.pop();
    stk.push(n + 1); m[n + 1] = ninf;
    for (int i = n; i >= 1; --i) {
        while (m[stk.top()] >= m[i]) {
            stk.pop(); 
        }
        r[i] = r[stk.top()] + (stk.top() - i) * m[i];
        stk.push(i);
    }
    ll ans = 0;
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        // 如果选择i作为转折点, 则值 = l[i - 1] + r[i]
        ll cur = l[i - 1] + r[i];
        if (cur > ans) {
            ans = cur;
            k = i;
        }
    }
    a[k] = m[k];
    // 处理左边
    for (int i = k - 1; i >= 1; --i) {
        a[i] = min(a[i + 1], m[i]);
    }
    // 处理右边
    for (int i = k + 1; i <= n; ++i) {
        a[i] = min(a[i - 1], m[i]);
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << ' ';
    }
    return 0;
}