解法

実はいくつかの連続する空でない部分列 \(B_1 , B_2 , \ldots , B_K\)に分割する際に、各 \(B_i\) は単調増加列または単調減少列として考えて良いとわかります。

よって、 この問題は以下の様に言い換えられます。

以下の条件を満たす様にスコア \(|A_{i+1}-A_i|\) を持つ要素 \(C_i\) ( \(i=1, \ldots , N-1\) ) を選んでいく事を考えます。

• \(A_i < A_{i+1}\) かつ \(A_{i+1} > A_{i+2}\) の時、 \(C_i\) または \(C_{i+1}\) のどちらかしか選べない
• \(A_i > A_{i+1}\) かつ \(A_{i+1} < A_{i+2}\) の時、 \(C_i\) または \(C_{i+1}\) のどちらかしか選べない
• 各 \(C_i\) は一回ずつしか 選べない

選んだ \(C_i\) のスコアの総和の最大値を求めなさい。

これは下記のような動的計画法によって解くことができます。

動的計画法で使う配列 \(\mathrm{dp}\) を以下の様に定める。

• \(\mathrm{dp}[i] [0]:=\) \(i\) 番目の要素まで見て、\(C_i\) を選ばなかった時のスコアの総和の最大値
• \(\mathrm{dp}[i] [1]:=\) \(i\) 番目の要素 まで見て、\(C_i\) を選んだ時のスコアの総和の最大値

解として \(\mathrm{max}(\mathrm{dp}[N-1][0], \mathrm{dp}[N-1][1])\) を求める。

よって、この問題は \(\mathcal{O}(N)\) で解ける事が分かりました。

\(B_i\) を単調増加列または単調減少列として良い理由

\(B_i\) を \(B'_1 , B'_2\) の二つに分割した時

\[ \begin{array}{ll} L_1=\min(B'_1),& R_1=\max(B'_1),\\ L_2=\min(B'_1),& R_2=\max(B'_1),\\ L=\min(B_i),& R=\max(B_i) \end{array} \]

とおくと、スコアの総和は

\[ \begin{aligned} (R_1-L_1)+(R_2-L_2) &=(\max(R_1, R_2) - \min(L_1, L_2)) + (\min(R_1, R_2) - \max(L_1, L_2))\\ &= (R-L) + (\min(R_1, R_2) - \max(L_1, L_2)) \end{aligned} \]

となります。

ここで、 \(\min(R_1, R_2) - \max(L_1, L_2)\) は \([L_1, R_1] \cap [L_2, R_2] \neq \emptyset\) の時非負となる事から、 単調増加でも単調減少でもない \(B_i\) に対し、以下の分割を行ってもスコアの総和は減少しない事が確かめられます。（\(\mathrm{argmax}\), \(\mathrm{argmin}\) はそれぞれ最大/最小となる要素のインデックスを返す関数として定義されます）

• \(A_{i -1}< A_{i}\) かつ \(A_{i} > A_{i+1}\) となる \(A_i\) が存在する時
  • \(i\) 番目と \(\mathrm{argmax}(A_{i-1}, A_{i+1})\) 番目の間を境界に \(B_i\) を分割
• \(A_{i -1} > A_{i}\) かつ \(A_{i} < A_{i+1}\) となる \(A_i\) が存在する時
  
  • \(i\) 番目と \(\mathrm{argmin}(A_{i-1}, A_{i+1})\) 番目の間を境界に \(B_i\)を分割

よって \(B_i\) は 単調増加列、または単調減少列として考えて構わない事が分かりました。