Beautiful Towers II

The O(N^2) brute-force approach is slow because it repeatedly calculates sums for overlapping subarrays. We can optimize this by pre-calculating these sums. The key insight is that the total sum for a mountain with a peak at i can be decomposed into two independent subproblems: the maximum sum of a non-decreasing sequence ending at i and the maximum sum of a non-increasing sequence starting at i. These two sets of sums (for all i) can be computed efficiently in O(N) time using a monotonic stack. After pre-computation, we can find the maximum total sum in a final O(N) pass.

• Define two arrays, leftSum and rightSum, of size n to store precomputed sums.
• Calculate leftSum: leftSum[i] will store the maximum sum of a valid non-decreasing sequence of towers on maxHeights[0...i] with i as the peak.
  • Use a monotonic stack (storing indices of maxHeights with increasing values) and iterate from i = 0 to n-1.
  • For each i, pop from the stack while maxHeights[stack.peek()] >= maxHeights[i].
  • The sum leftSum[i] can then be calculated in O(1) using the previously computed sum for the new stack top (leftSum[p]) and the value maxHeights[i].
• Calculate rightSum: rightSum[i] will store the maximum sum of a valid non-increasing sequence of towers on maxHeights[i...n-1] with i as the peak.
  • This is symmetric to the leftSum calculation. Use a monotonic stack and iterate from i = n-1 down to 0.
• Combine Results: The maximum sum for a mountain with peak i is leftSum[i] + rightSum[i] - maxHeights[i] (subtracting maxHeights[i] because it's included in both sums).
• Iterate through all i from 0 to n-1, calculate this combined sum, and find the maximum value. This will be the final answer.

This approach is based on dynamic programming and a monotonic stack. We pre-calculate two arrays:

1. leftSum[i]: The maximum sum of a beautiful tower configuration for the prefix maxHeights[0...i] where the heights are non-decreasing (i.e., i is the peak of this prefix). We can compute this for all i in O(N) time. We iterate from left to right, maintaining a monotonic stack of indices where maxHeights values are increasing. For each i, we find the previous index p where maxHeights[p] < maxHeights[i]. All towers between p and i will have height maxHeights[i]. The total sum leftSum[i] can be derived from leftSum[p].

2. rightSum[i]: Similarly, this is the maximum sum for the suffix maxHeights[i...n-1] where heights are non-increasing. This is calculated symmetrically by iterating from right to left.

Once both leftSum and rightSum arrays are populated, we can find the maximum possible sum for a mountain with a peak at index i by the formula: leftSum[i] + rightSum[i] - maxHeights.get(i). We subtract maxHeights.get(i) because it was counted in both leftSum[i] and rightSum[i]. The final answer is the maximum value of this expression over all i from 0 to n-1.

import java.util.List;
import java.util.Stack;

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        
        long[] leftSum = new long[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            long currentMaxHeight = maxHeights.get(i);
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                leftSum[i] = (long)(i + 1) * currentMaxHeight;
            } else {
                int prevSmallerIndex = stack.peek();
                leftSum[i] = leftSum[prevSmallerIndex] + (long)(i - prevSmallerIndex) * currentMaxHeight;
            }
            stack.push(i);
        }
        
        long[] rightSum = new long[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            long currentMaxHeight = maxHeights.get(i);
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                rightSum[i] = (long)(n - i) * currentMaxHeight;
            } else {
                int nextSmallerIndex = stack.peek();
                rightSum[i] = rightSum[nextSmallerIndex] + (long)(nextSmallerIndex - i) * currentMaxHeight;
            }
            stack.push(i);
        }
        
        long maxTotalSum = 0;
        for (int i = 0; i < n; i++) {
            maxTotalSum = Math.max(maxTotalSum, leftSum[i] + rightSum[i] - maxHeights.get(i));
        }
        
        return maxTotalSum;
    }
}