\(S_{i, j}\) を \((A_i, A_{i+1}\ldots, A_{j-1})\) のスコアとすると、\(S\) は anti-Monge になります。これは、\((\max_{i \leq k < j} A_k)\) および \((-\min_{i \leq k < j} A_k)\) が anti-Monge であることから従います。\(S_{i,j}\) は Sparse Table を用いることで \(O(1)\) で計算できます。

分割統治により公式解説と同様の dp を計算します。

\(i=l, \ldots, m-1\) および \(j = m, \ldots, r-1\) のうち \(i+2 \leq j\) を満たすものに対し、\(\mathrm{dp}[j] \leftarrow \mathrm{dp}[i] + S_{i,j}\) が遷移できれば良いです。\(i=m-1\) の場合のみ別で遷移することにすれば \(i+2 \leq j\) は無視できます。\((\mathrm{dp}[i] + S_{i,j})\) もまた anti-Monge になることから、SMAWK algorithm などを適用することで各 \(j=m, \ldots, r-1\) に対し \(\min_{l \leq i < m-1}(\mathrm{dp}[i] + S_{i,j})\) を効率的に求められます。

このアルゴリズムは \(O(N \log N)\) で動作し、十分高速です。