To maximize the sum while forming a mountain, for each possible peak, we want to keep the tallest possible towers to the left and right, but never exceeding the peak. We use monotonic stacks to efficiently compute the maximum sum for each peak.

Approach

For each index, compute the maximum sum to the left (including itself) where heights are non-increasing towards the peak.
Similarly, compute the maximum sum to the right.
For each index, the total sum is left sum + right sum - heights[i] (since the peak is counted twice).
Return the maximum total sum.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    long long maximumSumOfHeights(vector<int>& h) {\n        int n = h.size();\n        vector<long long> left(n), right(n);\n        stack<int> st;\n        for (int i = 0; i < n; ++i) {\n            while (!st.empty() && h[st.top()] > h[i]) st.pop();\n            if (st.empty()) left[i] = 1LL * h[i] * (i + 1);\n            else left[i] = left[st.top()] + 1LL * h[i] * (i - st.top());\n            st.push(i);\n        }\n        while (!st.empty()) st.pop();\n        for (int i = n - 1; i >= 0; --i) {\n            while (!st.empty() && h[st.top()] > h[i]) st.pop();\n            if (st.empty()) right[i] = 1LL * h[i] * (n - i);\n            else right[i] = right[st.top()] + 1LL * h[i] * (st.top() - i);\n            st.push(i);\n        }\n        long long ans = 0;\n        for (int i = 0; i < n; ++i) ans = max(ans, left[i] + right[i] - h[i]);\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func maximumSumOfHeights(h []int) int64 {\n    n := len(h)\n    left := make([]int64, n)\n    right := make([]int64, n)\n    st := []int{}\n    for i := 0; i < n; i++ {\n        for len(st) > 0 && h[st[len(st)-1]] > h[i] {\n            st = st[:len(st)-1]\n        }\n        if len(st) == 0 {\n            left[i] = int64(h[i]) * int64(i+1)\n        } else {\n            left[i] = left[st[len(st)-1]] + int64(h[i])*int64(i-st[len(st)-1])\n        }\n        st = append(st, i)\n    }\n    st = []int{}\n    for i := n - 1; i >= 0; i-- {\n        for len(st) > 0 && h[st[len(st)-1]] > h[i] {\n            st = st[:len(st)-1]\n        }\n        if len(st) == 0 {\n            right[i] = int64(h[i]) * int64(n-i)\n        } else {\n            right[i] = right[st[len(st)-1]] + int64(h[i])*int64(st[len(st)-1]-i)\n        }\n        st = append(st, i)\n    }\n    ans := int64(0)\n    for i := 0; i < n; i++ {\n        if left[i]+right[i]-int64(h[i]) > ans {\n            ans = left[i] + right[i] - int64(h[i])\n        }\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public long maximumSumOfHeights(int[] h) {\n        int n = h.length;\n        long[] left = new long[n], right = new long[n];\n        Deque<Integer> st = new ArrayDeque<>();\n        for (int i = 0; i < n; ++i) {\n            while (!st.isEmpty() && h[st.peek()] > h[i]) st.pop();\n            if (st.isEmpty()) left[i] = 1L * h[i] * (i + 1);\n            else left[i] = left[st.peek()] + 1L * h[i] * (i - st.peek());\n            st.push(i);\n        }\n        st.clear();\n        for (int i = n - 1; i >= 0; --i) {\n            while (!st.isEmpty() && h[st.peek()] > h[i]) st.pop();\n            if (st.isEmpty()) right[i] = 1L * h[i] * (n - i);\n            else right[i] = right[st.peek()] + 1L * h[i] * (st.peek() - i);\n            st.push(i);\n        }\n        long ans = 0;\n        for (int i = 0; i < n; ++i) ans = Math.max(ans, left[i] + right[i] - h[i]);\n        return ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun maximumSumOfHeights(h: IntArray): Long {\n        val n = h.size\n        val left = LongArray(n)\n        val right = LongArray(n)\n        val st = ArrayDeque<Int>()\n        for (i in 0 until n) {\n            w

Related Tags