老榕树智能建站软件,三水专业网站建设哪家好,网络推广有哪些,精准营销的概念给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i #xff0c;高度为 heights[i] 。 如果以下条件满足#xff0c;我们称这些塔是 美丽 的#xff1a; 1 heights[i] maxHeights[i]heights 是一个 山脉… 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i 高度为 heights[i] 。 如果以下条件满足我们称这些塔是 美丽 的 1 heights[i] maxHeights[i]heights 是一个 山脉 数组。 如果存在下标 i 满足以下条件那么我们称数组 heights 是一个 山脉 数组 对于所有 0 j i 都有 heights[j - 1] heights[j]对于所有 i k n - 1 都有 heights[k 1] heights[k] 请你返回满足 美丽塔 要求的方案中高度和的最大值 。 示例一 输入maxHeights [5,3,4,1,1]
输出13
解释和最大的美丽塔方案为 heights [5,3,3,1,1] 这是一个美丽塔方案因为
- 1 heights[i] maxHeights[i]
- heights 是个山脉数组峰值在 i 0 处。
13 是所有美丽塔方案中的最大高度和。示例二 输入maxHeights [5,3,4,1,1]
输出13
解释和最大的美丽塔方案为 heights [5,3,3,1,1] 这是一个美丽塔方案因为
- 1 heights[i] maxHeights[i]
- heights 是个山脉数组峰值在 i 0 处。
13 是所有美丽塔方案中的最大高度和。解题思路对山状数组进行分析 发现山状数组在最大值前为非递减最大值后为非递增枚举遍历数组中每个数字为最大值记录获得的最大值。
代码
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {int n maxHeights.size();long long res 0;for (int i 0; i n; i) {int p maxHeights[i];long long sum p;for (int j i - 1; j 0; j--) {p min(p, maxHeights[j]);sum p;}int s maxHeights[i];for (int j i 1; j n; j) {s min(s, maxHeights[j]);sum s;}res max(res, sum);}return res;}
};
