P83923

美丽塔 Ⅱ

难度 6 级 动态规划入门 单调栈
讨论 统计 1通过 2提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。

选择一个范围内的塔,如果以下条件满足,我们称这些塔是 美丽 的:

1 \leq heights[i] \leq maxHeights[i]

对于所有 0 < j \leq i ,都有 heights[j - 1] \leq heights[j]

对于所有 i \leq k < n - 1 ,都有 heights[k + 1] \leq heights[k]

请你返回能够选择的 美丽塔 要求的方案中,高度和的最大值 。

输入

第一行一个整数 n

第2行一共n个整数,maxHeights[i]

输出

输出仅一个数,即所有塔高度的和

样例

样例 1
输入
5
5 3 4 1 1
输出
13
样例 2
输入
6
6 5 3 9 2 7
输出
22
样例 3
输入
6
3 2 5 5 2 3
输出
18

提示

n \leq 5×10^5 , 0 < maxHeights[i] \leq 10^9

来源

leetcode

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交