FastPrep
Problem · Array

Maximum Sum of Heights

Learn this problem
● HardAmazonONSITE INTERVIEW
See Amazon hiring insights

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: int[]) → long

Examples

Example 1

maxHeights = [5,3,4,1,1]return = 13

Choosing [5,3,3,1,1] forms a mountain with sum 13.

Example 2

maxHeights = [6,5,3,9,2,7]return = 22

More Amazon problems

drafts saved locally
public long maximumSumOfHeights(int[] maxHeights) {
  // write your code here
}
maxHeights[5,3,4,1,1]
expected13
checking account