\(N\)次正方行列 \(A\) であって \(A_{i, j}= a_j + (j - i)^2\) となるものを考えると、\(A\) はMongeです。

簡単に証明を書きます。\(B_{i, j} = a_j\)、\(C_{i, j} = (j - i)^2\)となる行列 \(B, C\) を考えます。\(B\) のMonge性は定義から明らかです。\(C\) については下凸関数 \(f(x) = x^2\) について \(C_{i, j} = f(j - i)\) の形となっているためこれもMongeであることが従います。\(A = B + C\) なので、\(A\) がMongeであることが従います。

したがって、Monge行列 \(A\) について各行の最小値を列挙せよという問題が解ければ元の問題を解くことができることがわかります。Monge行列は monotone （各行の最小値をとるインデックスが、行番号が大きいほど大きい）であることが知られており、これを用いて分割統治で上記の問題を解くことができます。（この手法は monotone minima と呼ばれ、より詳細なアルゴリズムは Mongeの手引書（tatyamさん）などに記載があります。）

実装例