\(2\) 次関数的な数列の重要な性質として、その連続部分列もまた \(2\) 次関数的な数列になります。この性質から、以下の操作を繰り返す貪欲法が正当となります。

• \(A\) の先頭を含む \(2\) 次関数的な連続部分列であって可能な限り長いものを見つけ、そこを切り出して取り除く。

上記のような連続部分列は、先頭から順に要素を見ていくことで特定できます。具体的な方法の \(1\) つとして、最初の \(3\) 要素から \(2\) 次関数を特定し、その \(2\) 次関数と一致するかを確かめながら連続部分列を伸ばしていけばよいです。

別の方法として、第 \(2\) 階差 \(B_i \coloneqq A_i - 2 A_{i + 1} + A_{i + 2}\) を用いると実装が楽になります。具体的には、\((A_L, A_{L + 1} \dots, A_R)\) が \(2\) 次関数的であることと \(B_L = B_{L + 1} = \dots = B_{R - 2}\) が同値となるので、 \(B\) の値を確かめながら連続部分列を伸ばしていけばよいです。

実装例 (Python)