Beautiful Towers II
You are given a 0-indexed array maxHeights of n integers.
You are tasked with building n towers in the coordinate line. The i^th 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 <= heights[i] <= maxHeights[i]heightsis 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 the maximum possible sum of heights of a beautiful configuration of towers.
Example 1
# # # # # # # # # # # # # # 5 3 4 1 1
Input
maxHeights = [5,3,4,1,1]Output
13One beautiful configuration with a maximum sum is heights = [5,3,3,1,1], which is a mountain with peak i = 0, and no configuration has a sum greater than 13.
Example 2
#
#
# #
# # #
# # # #
# # # #
# # # # #
# # # # # #
# # # # # #
6 5 3 9 2 7Input
maxHeights = [6,5,3,9,2,7]Output
22One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2], which is a mountain with peak i = 3, and no configuration has a sum greater than 22.
Constraints
- 1 <= n == maxHeights.length <= 10^5
- 1 <= maxHeights[i] <= 10^9