問題概要
整数 $N$ と長さ $N$ の整数列 $A$ が与えられる．最初スコアは $0$ である． 次の操作を，$A$ の長さが $1$ 以下になるまで繰り返す:
- $A$の (その時点で) 隣接する2項を選び，どちらも削除する． 2項の差の絶対値がスコアに加算される．
得られるスコアの最大値を求めよ．
制約
$2 \leq N \leq 3\times 10^5$，$1 \leq A_i \leq 10^9$
解
略解．click to open
$N$ が偶数の時
大きい方の半分をプラスに，小さい方の半分をマイナスにした和がスコアの上界． この上界が達成できる．
$N$ が奇数の時
最後に残る1個を決めると，その左右それぞれで，上記偶数の時と同じ議論になる． 最後に残る1個を，左から順に全部調べる．