\(B_i =\sum_{j=i}^{j+K-1}A_i\) と置くと、問題を以下のように言い換えることが出来ます。

長さ \(N-K+1\) の数列 \(B=(B_1,\ldots,B_{N-K+1})\) が与えられる。この中から、選んだどの二つの要素の距離も \(K\) 以上という条件を満たすように要素を \(i\) 個選ぶとき、選んだ要素の総和を最大化せよ。

分割統治でこの問題を解きます。\(\mathrm{dp}[l][r][x][y][i]\) を、列 \((B_l,B_{l+1},\ldots,B_{r-1})\) について、左から \(x\) 個の要素、右から \(y\) 個の要素を選べないという条件が課されたときの、要素を \(i\) 個選ぶときの選んだ要素の総和の最大値として定義します。

\(\mathrm{dp}[l][r][x][y]\) は、\(m=\frac{l+r}{2}\) としたとき \(\mathrm{dp}[l][m][x][*],\mathrm{dp}[m][r][*][y]\) から以下の方法で計算できます。

• \(j=0,\ldots,K-1\) について、\(\mathrm{dp}[l][m][x][j]\) と \(\mathrm{dp}[m][r][K-1-j][y]\) をマージする。これらのマージ結果の最大値を取れば \(\mathrm{dp}[l][r][x][y]\) が得られる。

マージの計算は、愚直に行うと重いので工夫が必要です。ここで必要な観察は \(\mathrm{dp}[l][r][x][y]\) は \(i\) について上に凸になっているということです。上に凸な二つの関数は、傾きを降順にソートすることで線形時間でマージが出来るので、傾きを管理することで高速にマージが行えます。

計算量は \(\mathrm{O}(NK^2\log N)\) です。