AtCoder ABC 125 D - Flipping Signs

問題

長さN(<=1e5)の整数列が与えられる。0-N-1までの添字iを選んでi, i+1の要素の符号を反転できる。この操作を任意の回数を行い、操作後の数列の総和を最大化せよ。

やりかた

まず、もともとの数列にある負の数の個数が偶数個の場合は操作によってすべて正（もしくは0）にできる。奇数個だとどうしても一つ残ってしまうが、操作をうまく行うと、符号がマイナスになる位置を好きに選ぶことができる。なので、数列中で絶対値の最小の要素をマイナスにしてあとはプラスにすればいい。

以下ソース。

int main(){
  int N;
  cin >> N;

  ll sum = 0;
  ll mv = LLINF;
  int minus = 0;
  for (int i = 0; i < N; i++){
    ll x;
    cin >> x;
    sum += abs(x);
    if (x < 0LL) minus++;
    mv = min(mv, abs(x));
  }
  if(minus % 2) sum -= (mv * 2LL); //絶対値最小のものを（すでに足している分もいれて）ひく
  cout << sum << endl;
  return 0;
}

はじめてのABC