Reputation: 23
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
Upvotes: 2
Views: 620
Reputation: 5409
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
Upvotes: 2