2866. Beautiful Towers II

You are given a 0-indexed array maxHeights of n integers.

You are tasked with building n towers in the coordinate line. The ith tower is built at coordinate i and has a height of heights[i].

A configuration of towers is beautiful if the following conditions hold:

1. 1 <= heights[i] <= maxHeights[i]
2. heights is a mountain array.

Array heights is a mountain if there exists an index i such that:

• For all 0 < j <= i, heights[j - 1] <= heights[j]
• For all i <= k < n - 1, heights[k + 1] <= heights[k]

Return the maximum possible sum of heights of a beautiful configuration of towers.

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& A) {
        int n = A.size();
        vector<long long> dpl(n), dpr(n);
        vector<pair<long long, long long>> st;
        long long sum = 0;
        for(int i = 0; i < n; i++) {
            int pos = i;
            while(st.size() and st.back().first > A[i]) {
                auto [val, p] = st.back(); st.pop_back();
                sum -= val * (pos - p);
                pos = p;
            }
            dpl[i] = sum;
            sum += 1ll * A[i] * (i - pos + 1);
            st.push_back({A[i], pos});
        }
        st.clear();
        sum = 0;
        for(int i = n - 1; i >= 0; i--) {
            int pos = i;
            while(st.size() and st.back().first > A[i]) {
                auto [val, p] = st.back(); st.pop_back();
                sum -= val * (p - pos);
                pos = p;
            }
            dpr[i] = sum;
            sum += 1ll * A[i] * (pos - i + 1);
            st.push_back({A[i], pos});
        }
        long long res = 0;
        for(int i = 0; i < n; i++) {
            res = max(res, dpl[i] + dpr[i] + A[i]);
        }
        return res;
    }
};