for (int len = 2; len <= n; ++ len) for (int i = 1; i+len-1 <= n; ++ i) {
   r[i] = a[i+len-1]-a[i+len-2]+max(r[i], a[i+len-2]-a[i-1]-max(l[i], r[i]));
	l[i] = a[i]-a[i-1]+max(l[i+1], a[i+len-1]-a[i]-max(l[i+1], r[i+1]));
}