Problem

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 themaximum possible sum of heights of a beautiful configuration of towers.

Examples

Example 1

1
2
3
4
5
6

Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2

1
2
3
4
5
6

Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3

1
2
3
4
5
6
7

Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

Constraints

  • 1 <= n == maxHeights.length <= 10^5
  • 1 <= maxHeights[i] <= 10^9

Solution

Method 1 – Monotonic Stack for Left and Right Limits (Peak at Each Index)

Intuition

For each possible peak, we want to maximize the sum of the mountain array, where each height does not exceed its maxHeights value and is non-decreasing to the peak and non-increasing after. We use monotonic stacks to efficiently compute the best possible sum for each peak.

Approach

  1. For each index, treat it as the peak.
  2. For the left side (including the peak), use a monotonic stack to ensure non-increasing heights and not exceeding maxHeights.
  3. For the right side, do the same in reverse.
  4. For each peak, sum the left and right contributions (subtracting the peak once as it is counted twice).
  5. Return the maximum sum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& h) {
        int n = h.size();
        long long ans = 0;
        for (int peak = 0; peak < n; ++peak) {
            vector<int> arr(n);
            arr[peak] = h[peak];
            for (int i = peak-1; i >= 0; --i)
                arr[i] = min(h[i], arr[i+1]);
            for (int i = peak+1; i < n; ++i)
                arr[i] = min(h[i], arr[i-1]);
            long long sum = 0;
            for (int x : arr) sum += x;
            ans = max(ans, sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func maximumSumOfHeights(h []int) int64 {
    n := len(h)
    ans := int64(0)
    for peak := 0; peak < n; peak++ {
        arr := make([]int, n)
        arr[peak] = h[peak]
        for i := peak-1; i >= 0; i-- {
            arr[i] = min(h[i], arr[i+1])
        }
        for i := peak+1; i < n; i++ {
            arr[i] = min(h[i], arr[i-1])
        }
        sum := int64(0)
        for _, x := range arr {
            sum += int64(x)
        }
        if sum > ans {
            ans = sum
        }
    }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long maximumSumOfHeights(int[] h) {
        int n = h.length;
        long ans = 0;
        for (int peak = 0; peak < n; ++peak) {
            int[] arr = new int[n];
            arr[peak] = h[peak];
            for (int i = peak-1; i >= 0; --i)
                arr[i] = Math.min(h[i], arr[i+1]);
            for (int i = peak+1; i < n; ++i)
                arr[i] = Math.min(h[i], arr[i-1]);
            long sum = 0;
            for (int x : arr) sum += x;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumSumOfHeights(h: IntArray): Long {
        val n = h.size
        var ans = 0L
        for (peak in 0 until n) {
            val arr = IntArray(n)
            arr[peak] = h[peak]
            for (i in peak-1 downTo 0) arr[i] = minOf(h[i], arr[i+1])
            for (i in peak+1 until n) arr[i] = minOf(h[i], arr[i-1])
            var sum = 0L
            for (x in arr) sum += x
            ans = maxOf(ans, sum)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maximumSumOfHeights(self, h: list[int]) -> int:
        n = len(h)
        ans = 0
        for peak in range(n):
            arr = [0]*n
            arr[peak] = h[peak]
            for i in range(peak-1, -1, -1):
                arr[i] = min(h[i], arr[i+1])
            for i in range(peak+1, n):
                arr[i] = min(h[i], arr[i-1])
            ans = max(ans, sum(arr))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn maximum_sum_of_heights(h: Vec<i32>) -> i64 {
        let n = h.len();
        let mut ans = 0i64;
        for peak in 0..n {
            let mut arr = vec![0; n];
            arr[peak] = h[peak];
            for i in (0..peak).rev() {
                arr[i] = h[i].min(arr[i+1]);
            }
            for i in peak+1..n {
                arr[i] = h[i].min(arr[i-1]);
            }
            let sum: i64 = arr.iter().map(|&x| x as i64).sum();
            ans = ans.max(sum);
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each peak, we scan the array left and right.
  • 🧺 Space complexity: O(n) — For the temporary array for each peak.