不能被M整除的数组元素的最大总和，deleting/avoiding至多K个连续数组元素

Question

给定：N、K、M 和 A（数组）

N = 数组中的元素数
K = 答案中可以avoided/not考虑的最大连续数组元素
|A| = N

从数组的最后一个索引开始，你必须找到使用数组元素可以获得的最大总和，使得总和在任何时刻都不能被 M 整除。可以通过从数组的最后一个索引遍历到第一个索引（顺序）来获取和，您可以选择include 该元素进入最终答案，或避免它。

有两个条件：

当一个项目是included时，到那一刻包含的所有元素的总和（包括正在包含的当前元素），应该不被 M.
当一个项目被避免时，必须记住你最多可以避免K个连续的数组元素一次。

注意：严格要求从最后一个索引开始，跳过任何索引都将计入可以避免的最大连续元素的限制（即K） .

如果在所有遍历实例中都满足这两个条件，就无法从最后一个索引遍历到第一个索引，我们只好return返回-1，否则 return 返回 可能的最大总和 。

约束：

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

示例 1：

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

Output : 5 + 4 + 2 = 11

示例 2：

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

Output = -1

示例 3：

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

Output : 7 + 6 + 2 + 4  = 19

Answer 1

我们可以使用 3-D 动态规划来解决这个问题，与另一个非常相似 post。这是我使用的公式的定义：

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

这个公式很长，因为 0 的初始空总和（技术上可以被 M 整除）是允许的，但所有其他的都不是。还有一个公式的初始值没有包含在上面：如果 A[N-1]（最后一个元素）不能被 M 整除，那么 dp[N-1][0][A[N-1]%M] 就是 A[N-1]。您可以将此公式缩短两行，但至少要匹配 4 个不同的模式。

时间和 space 复杂度为 O(NMK)，但是 space 复杂度可以降低到 O(MK) 通过仅存储 DP 的最后两行 table.

这是该 DP 公式的 Python 计算：

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

不能被M整除的数组元素的最大总和，deleting/avoiding至多K个连续数组元素

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

arrays

algorithm

math

dynamic-programming

subset-sum