题意
给你一个数组a[1..n]。有一个函数(f(l,r)=sum_{i=l}^{r-1}left| a[i]-a[i+1] ight| (-1)^{l-i}(1le l< rle n)),求f最大值。
题解
令b[i]=|a[i]-a[i+1]|(-1)^i,c[i]=-b[i]。那么答案就是b数组和c数组的最大子序列和中较大的一个。
代码
const int N=101000;
ll n,a[N],s;
ll ans,mb,mc;
int main() {
scanf("%lld",&n);
rep(i,0,n){
scanf("%lld",a+i);
if(i){
s+=abs(a[i-1]-a[i])*(i&1?1:-1);
mc=min(-s,mc);
mb=min(s,mb);
ans=max(s-mb,ans);
ans=max(-s-mc,ans);
}
}
printf("%lld
",ans);
return 0;
}