なるべく多くの点を含むような長方形をなす左上の点と右下の点の組み合わせを探す、また、そのような点の候補はある増加列の組に絞られる、という考察までは公式のスライドと同じなので省略します。

左上の \(i\) 番目の候補点と、右下の \(j\) 番目の候補点がなす長方形が含む点の数を \(f(i, j)\) と書きます。

右下の候補点 \(l, r (l < r)\) に着目します。\(g(i) = f(i, l) - f(i, r)\) に注目してみましょう。図を書いてみると、\(g\) は単調減少であることが分かります。 このことから、左上の点はある番号以降では \(r\) を右下とした方が \(l\) を右下とするよりも得であることが分かります。

このことから、\(f(i, j)\) は Monotone です。よって、分割統治法を用い、\(f(i, j)\) の値を Wavelet Matrix を用いて \(O(\log N)\) で計算できるようにすることで、全体で \(O(N \log ^ 2 N)\) で解くことができます。