算法1

(贪心) $O(n)$

结论（1）：通过观察显然可得：对于1个单调上升序列，其需要搭建的次数即为高度最高的那个数。

对于2个单调上升序列，例如 2 3 4 1 2 ， 最 小 次 数 是 5 ， 如果按（1个单调上升序列 ， 其需要搭建的次数即为高度最高的那个数），则答案是6，但是通过观察可得，其多出来的1正好是拐点，所以只需要减去1即可。

说明；如果拐点处为0，即为2 3 4 0 2，则一次操作只能要么对[1,3]操作，要么对[5]操作，即两个操作无关，可以直接分别用结论(1)。而如果为2 3 4 1 2,则对[4,5]处的操作可以包含进[1,3]中，所以需要减去[4]，减去后，变为1 2 3 0 1,此时只能对[1,3]操作，或对[5]操作，即此时[1,3]与[5]无关，分别使用结论(1)，3+1=4，再加上[4] (第一次进行的操作),4+[4]=5，所以为5次。

总结：总的来说，单调上升序列的拐点是对两个序列操作是否有关的关键，由于拐点的数可以包含进第一个单调上升序列中，所以减去后，两个上升序列无关，可以用结论(1)，然后再加上减去的这个拐点上的数。

由于所有序列可以看成单调上升，单调下降和单个数，而长度为n的单调下降序列可以看成n个长度为1的单调上升序列，单个数也可以看作长度为1的单调上升序列。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;

int n,a[N],b[N],s[N];
int cnt;//判断是否完成
int res;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        if(a[i]<a[i-1]){
            res+=a[i-1];
            res-=a[i];
        }

        if(i==n) res+=a[n];//最后一个点需要加上。
    }

    cout<<res;
    return 0;
}