1、正向思路：动态规划

令dp[i]表示：所取之和sum最大，且sum % k = i。

具体代码如下。注意每次状态转移之前，要备份一下dp数组。

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    long long a;
    cin >> n >> k;
    vector<long long> dp(k, LLONG_MIN);
    dp[0] = 0;
    while(n--) {
        cin >> a;
        vector<long long> tmp(k);
        for(int i = 0; i < k; ++i) {
            int j = (a + i) % k;
            tmp[j] = max(dp[j], dp[i] + a);
        }
        swap(dp, tmp);
    }
    cout << (dp[0] == 0 ? -1 : dp[0]);
}

2、反向思路：动态规划

换个思路，将数组的所有数字相加得到sum，计算mod = sum % k的值。

若mod == 0，那么直接输出sum。

否则本题可以转化为：从数组a中挑出若干个数，使其之和对k取余为mod，求这个和的最小值。

下面贴出代码。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    long long sum = 0;
    for (auto& i : a) {
        cin >> i;
        sum += i;
    }
    int mod = sum % k;
    if(mod == 0) {
        cout << sum;
        return 0;
    }
    vector<long long> dp(k, 1e13);
    dp[0] = 0;
    for(auto& i : a) {
        vector<long long> tmp(k);
        for(int j = 0; j < k; ++j) {
            int p = (i + j) % k;
            tmp[p] = min(dp[p], dp[j] + i);
        }
        swap(tmp, dp);
    }
    if(dp[mod] == 1e13 || dp[mod] == sum) {
        cout << -1;
    } else {
        cout << sum - dp[mod];
    }
}