【cf789C】Functions again（最大子序列和）

C.Functions again

題意

給你一個數組a[1..n]。有一個函數\(f(l,r)=\sum_{i=l}^{r-1}\left| a[i]-a[i+1]\right| (-1)^{l-i}(1\le l< r\le 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\n",ans);
	return 0;
}
           

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆