Let \(B_i =\sum_{j=i}^{j+K-1}A_i\), then the problem can be rephrased as follows:

You are given a sequence \(B=(B_1,\ldots,B_{N-K+1})\) of length \(N-K+1\). Choose \(i\) elements so that every pair of chosen elements is distant by \(K\), and maximize the sum of the chosen elements.

We solve the problem with Divide and Conquer. Let \(\mathrm{dp}[l][r][x][y][i]\) be the maximum sum of the chosen elements when choosing \(i\) elements from sequence \((B_l,B_{l+1},\ldots,B_{r-1})\), where it is disallowed to the leftmost \(x\) elements and rightmost \(y\) elements.

\((B_l,B_{l+1},\ldots,B_{r-1})\) can be computed based on \(\mathrm{dp}[l][m][x][*]\) and \(\mathrm{dp}[m][r][*][y]\), where \(m=\frac{l+r}{2}\), as follows:

• For \(j=0,\ldots,K-1\), merge \(\mathrm{dp}[l][m][x][j]\) and \(\mathrm{dp}[m][r][K-1-j][y]\). The maximum merge result is \(\mathrm{dp}[l][r][x][y]\).

Naive merge is slow, so it needs a speedup. An important observation is that \(\mathrm{dp}[l][r][x][y]\) is concave with respect to \(i\). Two concave functions can be merged in a linear time by sorting in descending order of their slopes, so they can be merged fast by managing the slopes.

The complexity is \(\mathrm{O}(NK^2\log N)\).