观察可以发现表达式中的正负性只和起点l
的奇偶性有关,也就是说从任意一个位置l
开始计算f
,
和从与它同奇偶的0
或1
开始计算f
,结果是一样的,这样问题就转化为了求最大连续子段和的问题。
从0
,1
分别开始做一遍即可
$time\ O(n)$
#include<iostream>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int a[N];
int n;
LL cal(int st)
{
LL res=INT_MIN;
LL last=INT_MIN;
int t;
for(int i=st;i<n-1;i++)
{
if((i-st)%2) t=-1;
else t=1;
last=max(last,0ll)+abs(a[i]-a[i+1])*t;
res=max(last,res);
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
LL res=max(cal(0),cal(1));
cout<<res<<endl;
return 0;
}