算法
(差分,贪心) $O(n)$
我们逆向思考：假设给定了每块积木的高度，每次可以将某一段区间中的所有高度减一，问最少操作多少次可以将所有高度变成0。
原序列是： $h_1, h_2, h_3, …, h_n$, 其中 $h_i \ge 1$。
构造差分序列：
$$ b_1 = h_1 \\\\ b_2 = h_2 - h_1 \\\\ b_3 = h_3 - h_2 \\\\ … \\\\ b_n = h_n - h_{n-1} \\\\ b_{n + 1} = -h_n $$
则将 $h_L, h_{L+1}, …, h_{R}$ 中的每个数减1的操作，等价于将 $b_L$ 减1, 将 $b_{R+1}$ 加1。关于差分算法可以参考 AcWing 797.。
因此问题变成每次从 $b_1, b_2, …, b_{n + 1}$ 中挑两个数，前一个减1，后一个加1，问最少操作多少次可以将所有数变成0。
首先，对于每个正数 $b_i > 0$，最少需要操作 $b_i$ 次，因此总操作次数一定不少于差分数组中所有正数之和 $B$。
然后我们构造一种操作方式，使得恰好可以通过 $B$ 次操作，将所有数变成0。 那么就可以说明最少操作次数一定是所有正数之和。
操作方式如下：
- 从后往前操作，如果当前的 $b_i > 0$，则将其减1，并将其后的某个负数加1。
由于 $\sum b_i = 0$，因此从数量上看，正数和负数是一一对应的。
然后我们考虑在操作过程中，对于每个正数 $b_i$，其后是否一定存在负数与之对应。由于差分数组的所有后缀 $\sum _{i = k} ^ {n + 1} b_i = -h_k \le 0$，因此在所有后缀中，正数之和一定小于等于负数之和，所以负数总是可以被找到的。
因此，上面的操作方式是合法的。
时间复杂度
求差分序列扫描一遍数组即可，因此总时间复杂度是 $O(n)$。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int h[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
int res = 0;
for (int i = n; i; i -- ) res += max(0, h[i] - h[i - 1]);
cout << res << endl;
return 0;
}
题目要求的输入有两行，一行是n,一行是数据.有一个样例是分成了三行，第一行是n，第二行是空格，第三行才是数据。所以用java的BufferedReader读数据过不了，只能用scanner
这里为什么还要把Bn+1算进来呢？平时再算的时候根本就不需要算这一项啊
Y总，既然后缀和一定<= 0, 那最后正数都减成0了，后面还有负数没有加为0怎么办？
这句话是怎么来的？样例的差分数组的和就不等于0啊？
因为差分数组末尾和开始都是零，中间部分只是他的变化量，所有变化之后开始是零结果是零，所以变化量之和是零
注意看到差分数组比平时多了一项bn+1，累加起来才能够等于零。