\(M = 10 \) として \(O(NM)\) で解く方法です。

まず \(f(k)\) を以下のように定義します。

• \(A_{i} - A_{j} = A_{j} - A_{k}\) かつ \(i<j<k\) を満たす、 \(j\) が存在する、 \(i\) の最大値。ただし、そのような \(i\) が存在しないなら \(0\) 。

すると求めるべき値は以下のようになります。

\[\sum_{k = 1}^{N} \max\left(f(1), f(2), \dots , f(k)\right)\]

よって、この \(f(k)\) が高速に求まれば良いです。

まず、全ての \(1\leq k\leq N, 1\leq a\leq M\) に対して、 \(A_{j} = a\) かつ \(j\lt k\) を満たす最大の \(j\) (存在しないなら \(0\) )を \(g(k,a)\) として、これを求めておきます。

\(k\) と \(A_{j}\) の値 \(v\) を固定したとき、 \(A_{i} - A_{j} = A_{j} - A_{k}\) かつ \(i < j < k\) を満たす最大の \(i\) は \(g(g(k,v),2v-A_{k})\) となります。

よって、\(v= 1,2,\dots M\) について、上記の値を求め、その最大値が \(f(k)\) となります。

上記を適切に実装すれば時間/空間計算量ともに \(O(NM)\) で求まります。

実装例 c++

また、全ての \(1\leq k\leq N, 1\leq a\leq M\) に対して、 \(2A_{j} - A_{i} = a\) かつ \(i < j <k \) を満たす \(j\) が存在する最大の \(i\) を適時更新しながら求めることで空間計算量を \(O(N+M)\) に抑えることができます。

実装例 c++

参考

shinchan さんのツイート

https://twitter.com/Sophia_maki/status/1749078099864727597

こちらの解法では \(l\) を固定して求めています。(自分の解説は \(r\) を固定して求めている)