Hello codeforces!

Assume an array and we start from element at index 0. We want to go from 0 index to last index of the array by taking steps of at max length K.

For example, suppose an array is [10,2,-10,5,20] and K is 2, which means maximum step length is 2 (We can assume K is always possible and less than length of array). Now as we start from index 0, our score currently is 10 and then we can either go to 2 or can go to -10. Suppose we go to 2 from here so total score becomes 10+2=12. Now from 2 we can go to -10 or 5 so you go to 5 making score 12+5=17. From here you directly go to last index as you have no way other than that, hence total score is 17+20=37.

For given array of length N and an integer K we need to find maximum score we can get. I thought of a solution, to divide it into sub problems by deciding weather to go at index i or not and recursively call the remaining array. But I sense some dynamic programming out of this problem.

How can this be solved for given array of size N and integer K.

Constraint : 1<=N<=100000 and 1<=K<=N

Can someone suggest complexity lesser than O(n*k). Thanks!