选择 a[i]：如果选择当前的元素 a[i]，我们可以从前 i - 1 个元素中找到余数为 j 的情况。

  • 选择了 a[i] 之后，新的余数就是 (j + a[i]) % k。
  • 那么 dp[i][(j + a[i]) % k] 可以更新为 dp[i - 1][j] + a[i]，表示我们在余数为 j 的最大和的基础上加上当前元素 a[i]

    • 不选择 a[i]：

    • dp[i][(j + a[i]) % k] 维持原来的值，即 dp[i - 1][(j + a[i]) % k]。余数还是为上一个的余数
    #include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;
long long a[100010];
long long dp[N][N];

int main() {
    long long n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= n; j ++)
            dp[i][j] = -1e18;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < k; j ++){
            dp[i][(j + a[i]) % k] = max(dp[i - 1][j] + a[i], dp[i - 1][(j + a[i]) % k]);
        }
    }
    if(dp[n][0] <= 0) cout << -1;
    else cout << dp[n][0] << endl;
}