Auto comment: topic has been updated by AvaraKedavra (previous revision, new revision, compare).

There is a mistake in the last line, it should be best_i + sum(i+1,i+len) — k (it is written correctly in the sample code).

As for the reasoning, Suppose you want to find score of array of length len starting at index, then let rem=len%m. The your score would be sum(i,i+rem-1) -k + max(i+rem).

where max(i+rem) is the maximum score you can obtain if you are starting at index (i+rem) and your sub-array's length is multiple of m (i.e. m, 2m, 3m...)

Now, you can notice that max[i] = sum(i,i+m-1) + max[i+m]. Your base case would be max[n-m]= MAX(0, sum(n-m,n-1)], and max[i]=0 for all i greater than n-m and less than n-1.

After your max array is calculated you can go through all the indices and for each rem = 1,2,3....m, find out the maximum score.

Basically, the idea is: we want to apply one of the usual solutions to the maximum sum on subarray problem with an additional constraint.

The additional constraint is the following one: basically, we get $$$k$$$ penalty if the subarray contains at least $$$1$$$ element, additional $$$k$$$ penalty for a subarray containing at least $$$m+1$$$ elements, additional $$$k$$$ for a subarray with at least $$$2m+1$$$ elements, and so on.

Suppose we iterate on the left border of the subarray we're interested in. We can reduce some elements by $$$k$$$ to maintain the penalty. So, the first element which we decrease by $$$k$$$ will be the $$$1$$$-st after the left border; the second element will be the $$$(m+1)$$$-th after the left border, and so on.

Obviously, iterating on the left border is too slow, if we want to model these decreases and search for the best right border. However, we can instead iterate on the remainder of the left border modulo $$$m$$$, because this leads to similar decreases. If our left border $$$l$$$ has remainder modulo $$$m$$$ equal to $$$x$$$, then we need to decrease the $$$x$$$-th element of the array, the element $$$(x+m)$$$, the element $$$(x+2m)$$$, and so on.

And now we need to find the maximum sum on subarray with the remainder of $$$l$$$ modulo $$$m$$$ equal to $$$x$$$. We can modify our prefix sum approach to consider only such subarrays of follows: while we keep track of the minimum value of $$$p_l$$$, we consider only values of $$$l$$$ having $$$l \bmod m = x$$$.

So, this is how we get a solution in $$$O(nm)$$$.