Problem Link

I see various solutions involving segment tree, dp etc. I have a simple solution without using these stuffs, also which works for $$$0\le k \le n$$$.

If your subarray of size $$$m$$$ has $$$z$$$ elements to which $$$x$$$ is added and thus $$$m-z$$$ elements in which $$$x$$$ is subtracted then, the sum of subarray will be $$$s + 2zx - mx$$$. (Here $$$s$$$ is the sum of subarray before doing the operation). Now there are several cases to consider.

If $$$x \geq 0$$$. Then we want $$$2zx$$$ to be as large as possible, so, there are two further subcases

If $$$x \geq 0$$$ and $$$m \leq k$$$. Then, we should choose $$$z = m$$$. Sum $$$= s + mx$$$. To find this over all subarrays, just do the transformation, $$$a[i] = a[i] + x$$$ over all $$$i$$$, then find the maximum subarray sum in $$$a$$$.

If $$$x \geq 0$$$ and $$$m > k$$$. Then, we should choose $$$z = k$$$. Sum $$$= s + 2kx - mx$$$. To find this over all subarrays, just do the transformation, $$$a[i] = a[i] - x$$$ over all $$$i$$$, then find the maximum subarray sum in $$$a$$$ plus $$$2kx$$$.

If $$$x < 0$$$. Then we want $$$z$$$ to be as small as possible, so, there are two further subcases

If $$$x < 0$$$ and $$$n-m \leq k$$$. Then, $$$z$$$ has to be $$$k-n+m$$$. Sum $$$= s + 2x(k-n) + mx$$$. To find this over all subarrays, just do the transformation, $$$a[i] = a[i] + x$$$ over all $$$i$$$, then find the maximum subarray sum in $$$a$$$ plus $$$2x(k-n)$$$.

If $$$x < 0$$$ and $$$n-m > k$$$. Then, we should choose $$$z = 0$$$. Sum $$$= s- mx$$$. To find this over all subarrays, just do the transformation, $$$a[i] = a[i] - x$$$ over all $$$i$$$, then find the maximum subarray sum in $$$a$$$.

That's it! Its a simple solution. You can use deque for $$$O(n)$$$ solution or a multiset for $$$O(nlogn)$$$ solution. I hope you guys find it helpful :)

O(n) solution using deque