搭建积木

课程自编 · 差分思想

题目描述

有 $n$ 个位置，初始高度都是 $0$。每次操作可以选择一个连续区间 $[l,r]$，把其中每个位置的高度都增加 $1$。给出目标高度 $h_1,h_2,\dots,h_n$，求最少需要多少次操作。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $h_1,h_2,\dots,h_n$。

输出格式

输出一个整数，表示最少操作次数。

数据范围与约定

$1 \le n \le 2\times 10^5$，$0 \le h_i \le 10^9$。

样例输入

5
2 3 4 1 2

样例输出

5

样例说明

把高度看成差分：每段新的“上升”都需要一次新操作。答案为 $h_1+\sum_{i=2}^{n}\max(0,h_i-h_{i-1})=2+1+1+0+1=5.$

说明

课程自编题，数据由 src/gen.py 生成。