Beautiful Towers I

medium monotonic stack array prefix sums

Problem

Given heights of n towers, you may lower any tower (remove bricks) but never raise one. Reshape them into a mountain: heights are non-decreasing up to a peak (one or more equal towers) and then non-increasing. Return the maximum possible sum of the resulting heights.

Inputheights = [5, 3, 4, 1, 1]

Output13

Lower index 2 to make [5, 3, 3, 1, 1]; the peak sits at index 0. Sum = 5+3+3+1+1 = 13.

heights (comma-separated)

def maximumSumOfHeights(heights):
    n = len(heights)
    # prefix[i]: best sum of a non-decreasing run that peaks at i
    prefix = [0] * n
    stack, s = [], 0                  # stack of plateau indices, s = running sum
    for i in range(n):
        # lower every taller tower on the left down to heights[i]
        while stack and heights[stack[-1]] > heights[i]:
            j = stack.pop()
            width = j - (stack[-1] if stack else -1)
            s -= width * heights[j]
        width = i - (stack[-1] if stack else -1)
        s += width * heights[i]       # heights[i] now spans that plateau
        stack.append(i)
        prefix[i] = s
    # suffix[i]: best sum of a non-increasing run that peaks at i (mirror)
    suffix = [0] * n
    stack, s = [], 0
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] > heights[i]:
            j = stack.pop()
            width = (stack[-1] if stack else n) - j
            s -= width * heights[j]
        width = (stack[-1] if stack else n) - i
        s += width * heights[i]
        stack.append(i)
        suffix[i] = s
    # join the two halves at each peak (count the peak once)
    return max(prefix[i] + suffix[i] - heights[i] for i in range(n))

function maximumSumOfHeights(heights) {
  const n = heights.length;
  // prefix[i]: best sum of a non-decreasing run that peaks at i
  const prefix = new Array(n).fill(0);
  let stack = [], s = 0;             // stack of plateau indices
  for (let i = 0; i < n; i++) {
    // lower every taller tower on the left down to heights[i]
    while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
      const j = stack.pop();
      const width = j - (stack.length ? stack[stack.length - 1] : -1);
      s -= width * heights[j];
    }
    const width = i - (stack.length ? stack[stack.length - 1] : -1);
    s += width * heights[i];          // heights[i] spans that plateau
    stack.push(i);
    prefix[i] = s;
  }
  // suffix[i]: best sum of a non-increasing run that peaks at i (mirror)
  const suffix = new Array(n).fill(0);
  stack = []; s = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
      const j = stack.pop();
      const width = (stack.length ? stack[stack.length - 1] : n) - j;
      s -= width * heights[j];
    }
    const width = (stack.length ? stack[stack.length - 1] : n) - i;
    s += width * heights[i];
    stack.push(i);
    suffix[i] = s;
  }
  // join the two halves at each peak (count the peak once)
  let best = 0;
  for (let i = 0; i < n; i++) best = Math.max(best, prefix[i] + suffix[i] - heights[i]);
  return best;
}

long maximumSumOfHeights(int[] heights) {
    int n = heights.length;
    // prefix[i]: best sum of a non-decreasing run that peaks at i
    long[] prefix = new long[n];
    Deque<Integer> stack = new ArrayDeque<>();
    long s = 0;                       // running sum of the plateau model
    for (int i = 0; i < n; i++) {
        // lower every taller tower on the left down to heights[i]
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
            int j = stack.pop();
            long width = j - (stack.isEmpty() ? -1 : stack.peek());
            s -= width * heights[j];
        }
        long width = i - (stack.isEmpty() ? -1 : stack.peek());
        s += width * heights[i];
        stack.push(i);
        prefix[i] = s;
    }
    // suffix[i]: best sum of a non-increasing run that peaks at i (mirror)
    long[] suffix = new long[n];
    stack.clear(); s = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
            int j = stack.pop();
            long width = (stack.isEmpty() ? n : stack.peek()) - j;
            s -= width * heights[j];
        }
        long width = (stack.isEmpty() ? n : stack.peek()) - i;
        s += width * heights[i];
        stack.push(i);
        suffix[i] = s;
    }
    long best = 0;                    // join the two halves at each peak
    for (int i = 0; i < n; i++) best = Math.max(best, prefix[i] + suffix[i] - heights[i]);
    return best;
}

long long maximumSumOfHeights(vector<int>& heights) {
    int n = heights.size();
    // prefix[i]: best sum of a non-decreasing run that peaks at i
    vector<long long> prefix(n, 0);
    vector<int> stack;
    long long s = 0;                  // running sum of the plateau model
    for (int i = 0; i < n; i++) {
        // lower every taller tower on the left down to heights[i]
        while (!stack.empty() && heights[stack.back()] > heights[i]) {
            int j = stack.back(); stack.pop_back();
            long long width = j - (stack.empty() ? -1 : stack.back());
            s -= width * heights[j];
        }
        long long width = i - (stack.empty() ? -1 : stack.back());
        s += width * heights[i];
        stack.push_back(i);
        prefix[i] = s;
    }
    // suffix[i]: best sum of a non-increasing run that peaks at i (mirror)
    vector<long long> suffix(n, 0);
    stack.clear(); s = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && heights[stack.back()] > heights[i]) {
            int j = stack.back(); stack.pop_back();
            long long width = (stack.empty() ? n : stack.back()) - j;
            s -= width * heights[j];
        }
        long long width = (stack.empty() ? n : stack.back()) - i;
        s += width * heights[i];
        stack.push_back(i);
        suffix[i] = s;
    }
    long long best = 0;               // join the two halves at each peak
    for (int i = 0; i < n; i++) best = max(best, prefix[i] + suffix[i] - heights[i]);
    return best;
}

Explanation

Fix any index i as the peak. To its left the heights must be non-decreasing, so the best we can do is, scanning left from i, never exceed the running cap — each tower keeps its own height unless a later (closer to the peak) tower is shorter, which forces it down. The right half is the mirror. The brute-force way tries every peak and walks both directions in O(n), giving O(n²) — fine for n ≤ 10³, but a monotonic stack does it in O(n).

Prefix pass. We sweep left to right keeping a stack of indices whose heights are non-decreasing, together with a running sum s of the "lowered" arrangement that peaks at the current index. When a new tower heights[i] is shorter than the tower on top of the stack, that taller tower (and the whole plateau it represents) must be lowered to heights[i]. We pop it, subtract its old contribution width × heights[j], and repeat.

After popping, the segment from the new stack top up to i all becomes heights[i], so we add width × heights[i] and push i. That running sum is exactly prefix[i]: the largest non-decreasing total that ends at i.

Suffix pass. Run the identical logic from right to left to get suffix[i], the largest non-increasing total that starts at i. Now a mountain peaking at i has total prefix[i] + suffix[i] − heights[i] (the peak is counted in both halves, so subtract it once). The answer is the maximum over all i.

For [5, 3, 4, 1, 1] the best peak is index 0: the left half is just 5, and the right half forced down to a non-increasing shape is 5, 3, 3, 1, 1, summing to 13.

Time: O(n) Space: O(n)