Maximum Sum of Heights
Problem statement
Given positive maximum heights maxHeights, choose a positive height for every index so that height[i] <= maxHeights[i]. The resulting array must be mountain-shaped: for some peak index, heights do not decrease before the peak and do not increase after it.
Return the maximum possible sum of the chosen heights.
Interview follow-up
The interviewer asked follow-up questions about the approach, complexity, and possible alternatives.
Function
maximumSumOfHeights(maxHeights: List<Integer>) → longExamples
Example 1
maxHeights = [5,3,4,1,1]return = 13Choosing [5,3,3,1,1] forms a mountain with sum 13.
Example 2
maxHeights = [6,5,3,9,2,7]return = 22Constraints
1 <= maxHeights.length <= 10^51 <= maxHeights[i] <= 10^9