题解 | #小红取数#

import java.util.Scanner;

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[] arr = new long[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = sc.nextLong();
        }
        long[][] dp = new long[n+1][k];
        for(int i=0;i<=n;i++)
            Arrays.fill(dp[i],Long.MIN_VALUE);
        //初始化dp[0][0]，求其他的dp会用到
        dp[0][0]=0;
        for(int i=1;i<n+1;i++)
            for(int j=0;j<k;j++){
                //dp[i][j]表示前i个元素余数为j时的最大和
                //转移方程为dp[i][j] = 前i-1个元素余数为j的情况,即不选择当前元素
                //或者前i-1个元素选择当前元素后相加余数为j的情况
                dp[i][(int)((j+arr[i])%k)]=Math.max(dp[i-1][(int)((j+arr[i])%k)],dp[i-1][j]+arr[i]);
            }
            if(dp[n][0]>0){
                System.out.println(dp[n][0]);
            }else{
                System.out.println(-1);
            }
    }
}