Maximum Sum of elements of array which is not divisible by M, deleting/avoiding at most K consequtive array elements

Question

Given: N, K, M and A(array)

N = No. of elements in the array
K = Maximum consequtive array elements that can be avoided/not considered in the answer
|A| = N

Starting from the last index of the array, you have to find the maximum sum that can be obtained by using the elements of the array, such that at any instant the sum is not divisibe by M. The sum can be aquired by traversing from the last index to the first index of the array (in order), and you have a choice to either include that element into the final answer, or avoid it.

There are two conditions :

1. When an item is included, the total sum of all elements included till that moment (including the current element that is being included), should not be divisible by M.
2. When an item is avoided, it has to be kept in mind that you can avoid at most K consequtive array elements at once.

Note : It is strictly required to start from the last index, and skipping any index will count towards the limit on the maximum consequtive elements that can be avoided (i.e K).

If there exists no way to traverse from the last index to the first index by satisfying the two conditions at all instances of the traversal, we have to return back -1, or else return back the maximum sum possible.

Constraints :

2 <= N <= 10^5 
1 <= K <= 10
1 <= M <= 20

Example 1 :

N = 5
K = 1 
M = 2
A = [1, 2, 3 ,4, 5]

Output : 5 + 4 + 2 = 11

Example 2 :

N = 5
K = 2
M = 2
A = [3, 4, 2, 6, 8]

Output = -1

Example 3 :

N = 7
K = 2 
M = 2
A = [1,4,2,6,3,7,7]

Output : 7 + 6 + 2 + 4  = 19

Answer 1

We can do 3-D dynamic programming to solve this, very similarly to the other post. Here's the definition of the formula I'm using:

Let dp[i][k][r], 0 <= i < N, 0 <= k <= K, 0 <= r < M
be the maximum valid sum achievable after processing indices [i, i+1, ..., N-1]
such that index i is our kth consecutive skip and the sum's remainder is r (mod M).
We want max(dp[0][_][_])

dp[i][k][r] = -INF            if k + i > N
            = -INF            if r == 0 and k + i /= N
            = -INF            if r /= 0 and k + i == N
            = 0               if r == 0 and k + i == N
            = dp[i+1][k-1][r] if k > 0  and r /= 0

            = A[i] + max(dp[i+1][j][(r-A[i]) % M] over all j), if k == 0

The formula is quite long, due to the fact that the initial empty sum of 0 (which is technically divisible by M) is allowed but all others are not. There's also an initial value of the formula not included above: if A[N-1] (the last element) is not divisible by M, then dp[N-1][0][A[N-1]%M] is A[N-1]. You can shorten this formula by two lines, but you do have at least 4 distinct patterns to match.

The time and space complexity are O(NMK), but the space complexity can be reduced to O(MK) by only ever storing the last two rows of your DP table.

Here's a Python computation of that DP formula:

def f(A: List[int], N: int, K: int, M: int) -> int:
    assert N == len(A)

    if M == 1:
        return -1

    dp = [[[-math.inf for _ in range(M)] for _ in range(K + 1)] for _ in range(N)]

    for i in range(N):
        k = N - i
        if 0 <= k <= K:
            dp[i][k][0] = 0

    if A[N - 1] % M != 0:
        dp[N - 1][0][A[N - 1] % M] = A[N - 1]

    for i in reversed(range(N - 1)):
        elem = A[i]

        # When k == 0
        for r in range(1, M):
            for j in range(K + 1):
                dp[i][0][r] = max(dp[i][0][r], elem + dp[i + 1][j][(r - elem) % M])

        # When k > 0
        for k in range(1, K + 1):
            for r in range(1, M):
                dp[i][k][r] = dp[i + 1][k - 1][r]

    ans = max([max(x) for x in dp[0]])

    return ans if math.isfinite(ans) else -1

If you'd like to test this code and other answers, plus a slow brute force solution, here's an online code-runner