单调栈

显然，数组的形状为一个凸函数，那么可以枚举每个点作为凸函数的最高点。
凸函数最高点为i时，其右部元素 j > i 的最优取值为 min(mi , mi+1 , … , mj)
其左部元素k < i 的最优取值 min(mk,mk+1,...., mi)。
设b[i]为最高点为m[i]时其右部元素和。c[i]为其左部元素和。可以用单调栈一次扫描更新出这两组元素。
那么最高点选取 b[i] + c[i] - m[i]最大的元素，其向两侧更新即可

python3 代码

n = int(input())
m = [int(y) for y in input().split(' ')]
st = []
b = [0] * len(m)
c = [0] * len(m)
for i in reversed(range(len(m))):
    cur = m[i]
    while len(st) != 0 and m[st[-1][0]] > m[i]:
        st.pop()
    if len(st) != 0:
        cur += (abs(i - st[-1][0]) - 1 ) * m[i] + st[-1][1]
    else:
        cur += (len(m) - i - 1) * m[i]
    b[i] = cur
    st.append((i , cur))
st.clear()
for i in range(len(m)):
    cur = m[i]
    while len(st) != 0 and m[st[-1][0]] > m[i]:
        st.pop()
    if len(st) != 0:
        cur += (abs(i - st[-1][0]) - 1) * m[i] + st[-1][1]
    else:
        cur += i * m[i]
    c[i] = cur
    st.append((i,cur))
index = -1
for i in range(len(m)):
    if index == -1 or (b[i] + c[i] - m[i]) > (b[index] + c[index] - m[index]):
        index = i
for i in reversed(range(0,index)):
    m[i] = min(m[i] , m[i + 1])
for i in range(index + 1 , len(m)):
    m[i] = min(m[i] , m[i - 1])
for i in m :
    print(i , end=' ')
print()