2866. Beautiful Towers II Medium

1/**
2 * [2866] Beautiful Towers II
3 *
4 * You are given a 0-indexed array maxHeights of n integers.
5 * 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].
6 * A configuration of towers is beautiful if the following conditions hold:
7 * <ol>
8 * 	1 <= heights[i] <= maxHeights[i]
9 * 	heights is a mountain array.
10 * </ol>
11 * Array heights is a mountain if there exists an index i such that:
12 * 
13 * 	For all 0 < j <= i, heights[j - 1] <= heights[j]
14 * 	For all i <= k < n - 1, heights[k + 1] <= heights[k]
15 * 
16 * Return the maximum possible sum of heights of a beautiful configuration of towers.
17 *  
18 * <strong class="example">Example 1:
19 * 
20 * Input: maxHeights = [5,3,4,1,1]
21 * Output: 13
22 * Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
23 * - 1 <= heights[i] <= maxHeights[i]  
24 * - heights is a mountain of peak i = 0.
25 * It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.
26 * <strong class="example">Example 2:
27 * 
28 * Input: maxHeights = [6,5,3,9,2,7]
29 * Output: 22
30 * Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
31 * - 1 <= heights[i] <= maxHeights[i]
32 * - heights is a mountain of peak i = 3.
33 * It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.
34 * <strong class="example">Example 3:
35 * 
36 * Input: maxHeights = [3,2,5,5,2,3]
37 * Output: 18
38 * Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
39 * - 1 <= heights[i] <= maxHeights[i]
40 * - heights is a mountain of peak i = 2. 
41 * Note that, for this configuration, i = 3 can also be considered a peak.
42 * It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.
43 * 
44 *  
45 * Constraints:
46 * 
47 * 	1 <= n == maxHeights.length <= 10^5
48 * 	1 <= maxHeights[i] <= 10^9
49 * 
50 */
51pub struct Solution {}
52
53// problem: https://leetcode.com/problems/beautiful-towers-ii/
54// discuss: https://leetcode.com/problems/beautiful-towers-ii/discuss/?currentPage=1&orderBy=most_votes&query=
55
56// submission codes start here
57
58impl Solution {
59    pub fn maximum_sum_of_heights(max_heights: Vec<i32>) -> i64 {
60        
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_2866() {
72    }
73}
74