题解 | #小红取数#

C++代码，注意细节处理（dp初始化，长整型）： dp[i][(j+arr[i-1])%k]更新对余数的影响，选最大值：

要么加入arr[i-1]:选择余数为j的状态加上arr[i-1],即为新余数(j+arr[i-1])%k的最大值；

要么不加入arr[i-1], 选择前一个状态本来余数就是(j+arr[i-1])%k的值，作为新余数(j+arr[i-1])%k的最大值。

dp[i][(j+arr[i-1])%k] = max(dp[i-1][j]+arr[i-1], dp[i-1][(j+arr[i-1])%k]);

#include <iostream>
# include<vector>
# include<limits.h>
using namespace std;
class Solution{
public:
    long long maxSumOfK(vector<long long> arr, long long k){  // 注意返回的类型为long long
        int n = arr.size();
        // dp[i][j]表示前i个数截止，余数为j的最大和
        vector<vector<long long>> dp(n+1, vector<long long>(k, LONG_LONG_MIN));
        dp[0][0] = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<k;j++){ // 更新当前数带来的对所有余数的影响：
                // dp[i][(j+arr[i-1])%k]更新对余数的影响，选最大值：
                // 要么加入arr[i-1]:选择余数为j的状态加上arr[i-1],则对新余数(j+arr[i-1])%k产生影响，更新
                // 要么不加入arr[i-1], 选择前一个状态本来余数就是(j+arr[i-1])%k的值
                dp[i][(j+arr[i-1])%k] = max(dp[i-1][j]+arr[i-1], dp[i-1][(j+arr[i-1])%k]);
            }
        }
        if(dp[n][0]<=0) return -1;
        return dp[n][0];
    }
};
int main(){
    long long n,k;
    cin>>n>>k;
    vector<long long> arr(n); // 必须指定数组长度后，才能使用for循环cin>>arr[i]
    for(int i=0;i<n;i++) cin>>arr[i];
    Solution solve;
    cout<<solve.maxSumOfK(arr, k);  // 一定要注意返回的类型应该为long long
    return 0;
}