#include<bits/stdc++.h>
using namespace std;
long long a[100009];
int main(){
    long long n,b=0,c=0;
    cin>>n;
    //输入
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //差分
    for(int i=n;i>=1;i--)a[i]-=a[i-1];
    //计数
    for(int i=2;i<=n;i++){
        if(a[i]<0)c+=-1*a[i];
        else b+=a[i];
    }
    //输出最大值
    if(b>=c)cout<<b;
    else cout<<c;
    return 0;
}

时间复杂度O(n)

差分前缀和不会的立马去学！！！

根据差分可以将题翻译为：给一个差分数组用两个操作将这一数组除第一项意外的其他项变为0.

两个操作分别为

将差分数组

1:a[l]+=1；a[r+1]-=1;

2:a[l]-=1；a[r+1]+=1;

两个操作加起来就是让差分数组的一个位置-1一个位置+1；所以只要统计[2,n]内正的总和和负的总和取两者绝对值最大的那个输出就可以了(读者自证不难)。