002 - The Last Number on the Blackboard　解説

解説

　本問題の解答は $A_1 - A_2 + |A_3| + |A_4| + \cdots + |A_N|$ です。

　最終的に黒板に残る数は $\pm A_1 \pm A_2 \pm \cdots \pm A_N$ の形になりますが、問題の操作の性質上、$A_1$ は必ず $+$、$A_2$ は必ず $-$ の符号がつきます。一方で、$A_3, \dots, A_N$ の符号は、操作の順序を工夫することで任意に（それぞれ独立に）決定できます。 このことを示します。

任意の符号列を実現する手順

　$A_3, \dots, A_N$ の目標とする符号（$+$ または $-$）が与えられたとします（$A_2$ は必ず $-$ とします）。このとき、以下の 2 つのステップで操作を行うことで、目標の符号を実現できます。

1. $+$ の要素を左直近の $-$ の要素に結合する
   目標符号が $-$ である各要素（$A_2$ を含む）を起点とします。もしその右側に目標符号が $+$ である要素が連続している場合（例えば $A_k$ が $-$ で、$A_{k+1}, \dots, A_m$ が $+$ の場合）、$A_k$ に対して $A_{k+1}$ を引き、その結果から $A_{k+2}$ を引き……というように、左から順に引き算の操作を行います。
   これにより、これらの要素は $(A_k - A_{k+1} - A_{k+2} - \cdots - A_m)$ という 1 つの項にまとめられます。
2. まとめた項を $A_1$ から順次引く
   ステップ 1 をすべての $-$ の要素に対して行った後、黒板には $A_1$ と、ステップ 1 で作られたいくつかの項だけが残ります。これらを左から順に $A_1$ から引き算していきます。

正当性の確認

　ステップ 2 において、ステップ 1 で作られた項は最終的に $A_1$ から引かれるため、分配法則により展開すると $-(A_k - A_{k+1} - A_{k+2} - \cdots - A_m) = -A_k + A_{k+1} + A_{k+2} + \cdots + A_m$ となります。

　この展開式が示す通り、起点となった $A_k$ には $-$ の符号がつき、それに巻き込まれた $A_{k+1}, \dots, A_m$ にはすべて $+$ の符号がつきます。目標符号が $-$ で右に $+$ が続かなかった要素も、単独で引かれるため $-$ の符号が保たれます。
これにより、$A_3, \dots, A_N$ の各符号を自由にコントロールできることが示されました。

　各項の符号を自由に選べるのであれば、全体の値を最大化するためには、自身の値が正なら $+$、負なら $-$ の符号を割り当てる（＝すべての要素を絶対値にして足し合わせる）のが最適です。したがって、得られる最大値は $A_1 - A_2 + |A_3| + \cdots + |A_N|$ となります。

コード例

　以下はC++による想定解法のコードです。

#include <iostream>
using namespace std;
int main() {
  int n, ans = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a_i;
    cin >> a_i;
    if (i == 0) {
      ans += a_i;
    } else if (i == 1) {
      ans -= a_i;
    } else {
      ans += abs(a_i);
    }
  }
  cout << ans << endl;
  return 0;
}