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 :
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
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))
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments