$O(n)$

我们考虑差分数组,其实就是将所有的差分数组变成0,每次操作的就是选择差分数组里面的元素一个$+1$,一个$-1$,所以就等价于差分数组之中的所有的正整数元素之和。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];	
	}
	int res=0;
	for(int i=1;i<=n;i++)
	{
		res+=max(0,h[i]-h[i-1]);
	}
	cout<<res;
	return 0; 
}