每日一题：Functions again

题意

给定数组，求上述式子的最大值。

Solution

可以看出，上述式子是交替加减求最大子段和。预处理两项差的绝对值，那么只需要枚举起点是奇数位置还是偶数位置就可以了，根据贪心原则，起点肯定选正数，然后交替正负就好了，这样问题就转化成就求最大子段和了，贪心即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n;
ll a[N], b[N], d[N];
 
ll solve(ll c[]) {
  ll now = 0, ma = 0;
  for (int i = 2; i <= n; i++) {
    if (now <= 0)
      now = c[i];
    else
      now += c[i];
    ma = max(ma, now);
  }
  return ma;
}
 
int main() {
  cin >> n >> a[1];
  for (int i = 2; i <= n; i++) {
    cin >> a[i];
    ll x = llabs(a[i] - a[i - 1]);
    if (i & 1)
      b[i] = -x;
    else
      b[i] = x;
    d[i] = -b[i];
  }
  cout << max(solve(b), solve(d)) << endl;
  return 0;
}