leetcode-2865美丽塔

题目链接

2865. 美丽塔 I - 力扣（LeetCode）

解题思路

根据题意可以知道，假设数组的长度为n,对于山状数组heights定义如下：

• 假设heights[i]为数组中的最大值，则i左边的值均小于等于heights[i]，i右边的值均小于等于heights[i]；
• i的左侧，从0开始到i为非递归递减关系，即j属于[1,i]时，均满足heights[j-1]<=heights[j];
• i的右侧，从i开始到n-1为非递归关系，即j属于[i,n-2]时，均满足heights[j+1]<=heights[j];

题目给出了山状数组中每个元素的上限，即heights[i]<=maxheights[i]，题目要求返回的山状数组左右元素之和的最大值。根据以上分析可知：

• 对于j属于[0,i-1]时，此时max(heights[j]) = min(heights[j + 1], maxHeights[j]);
• 对于j属于[i+!,n-1]时，此时max(heights[j]) = min(heights[j -1],maxHeights[j]);
• 假设此时山状数组的山顶为heights[i]，此时整个山状数组的所有元素的最大值即可确定，此时山状数组的所有元素的最大值即可确定；
• 对于数组中的每个元素，尽量取最大值使得整个数组元素之和最大。

解题代码

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        res = 0
        for i in range(n):
            pre, psum = maxHeights[i], maxHeights[i]
            for j in range(i - 1, -1, -1):
                pre = min(pre, maxHeights[j])
                psum += pre
            suf = maxHeights[i]
            for j in range(i + 1, n):
                suf = min(suf, maxHeights[j])
                psum += suf
            res = max(res, psum)
        return res