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

CodePudding user response：

Just add a dimension. Let dp[i][k][m] represent the maximum sum achievable at the ith index with k skips that results in remainder m when divided by M. Something like (Python code):

def f(A, N, K, M):
  dp = [[[-float("inf")] * M for k in range(K   1)] for n in range(N)]   [[[0] * M for k in range(K   1)]]

  for k in range(1, K   1):
    for r in range(M):
      dp[N][k][r] = -float("inf")

  ans = -float("inf")

  for i in range(N-1,-1,-1):
    for k in range(0, min(N-i, K 1)):
      for r in range(M):
        if k > 0:
          dp[i][k][r] = dp[i 1][k-1][r]

        new_sum = A[i]   dp[i 1][k][r]
        new_r = (new_sum % M)

        if not isinstance(new_r, int):
          continue

        if k == 0:
          dp[i][k][new_r] = new_sum
          dp[i][k][0] = -float("inf")
          continue

        dp[i][k][new_r] = max(
          # skip (was assigned at
          # the top of the code block)
          dp[i][k][new_r],
          # include
          new_sum
         )

        dp[i][k][0] = -float("inf")

        ans = max(ans, dp[i][k][new_r])

  return ans if isinstance(ans, int) else -1

Output:

N = 7
A = [1,4,2,6,3,7,7]
K = 2
M = 2
# Output: 19
print(f(A, N, K, M))


N = 5
K = 1 
M = 2
A = [1, 2, 3 ,4, 5]
# Output : 5   4   2 = 11
print(f(A, N, K, M))


N = 5
K = 2
M = 2
A = [3, 4, 2, 6, 8]
# Output = -1
print(f(A, N, K, M))