This was asked in Airbus Aerothon 4.0 held on Hackerearth (ended on 15th May). I am paraphrasing the question:

We are given an array arr of positive elements, a positive integer k and a positive integer m. We can collect an element and add it to our score only if the resulting score is not divisible by m. We can skip at most k contiguous positions (we can skip any number of positions in total as long as we are not skipping more than k at a time). What is the maximum score possible? We start before the first element and have to reach the end. Return -1 if it's not possible.

Example 1:

arr : [1, 2, 3, 4, 5]
k: 2
m: 3

ans: 13

We take 1. Score = 1
We can't take 2, because score will become 3.
We take 3. Score = 1+3 = 4 ... and so on.

Example 2:

arr : [5, 4, 3, 2, 1]
k: 2
m: 3

ans: 11

Constraints:
n = len(arr)
0 < n < 10^4 or 10^5 (don't quite remember)
0 < k < 10
0 < m < 20

What I tried:
Thought it should be a straightforward DP problem but got totally confused trying to implement 😓
The solution I think would work has a time complexity of O(n * k^2) but that seems too big if n==10^5.

Starting from index 0, for every index i: for previous k elements check the maximum possible scores for each value of k, and store all of them in the current index. So each index will also contain k values. Only store the maximum value not divisible by m among those k values from each previous index.

i.e.,

...
for i in len(arr):
	for j in range(1, k+1):
		for value in dp[i-j]:
			dp[i].append(maximum (arr[i] + value) that is not divisible by m)
			
...
return max(dp[-1])

Would that have worked?

Please suggest better/correct ways to solve it.