题意整理。

• 给定一个数组，数组中所有元素均大于0。
• 现在要从数组中取出一些元素，使得和最大，并且和是k的倍数。求满足要求的最大和是多少。

方法一（二维dp）

1.解题思路

• 状态定义：首先定义一个二维dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和。
• 状态初始化：0个数时，最大和必为0，所以dp[0][0]=0。
• 状态转移：如果前一个状态余数为j，则更新当前余数为(j+arr[i])%k的情况，要么从余数为j的状态转化过来，要么前一个状态余数也是(j+arr[i])%k，即不选择当前元素。所以$dp\left[i\right]\left[\right(int\left)\right((j+arr[i\left]\right)dp[i][(int)((j+arr[i])\%k)]=Math.max(dp[i-1][j]+arr[i],dp[i-1][(int)((j+arr[i])\%k)])$dp[i][(int)((j+arr[i])。

图解展示：

2.代码实现

import java.util.*;

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();
        }
        //dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和
        long[][] dp=new long[n+1][k];
        for(int i=0;i<=n;i++){
            Arrays.fill(dp[i],Long.MIN_VALUE);
        }
        //状态初始化，0个数时，最大和必为0
        dp[0][0]=0;
        
        for(int i=1;i<=n;i++){
            for(int j=0;j<k;j++){
                /*如果前一个状态余数为j，则更新当前余数为(j+arr[i])%k的情况，要么从余数为j的状态转化过来，
                要么前一个状态余数也是(j+arr[i])%k，即不选择当前元素*/
                dp[i][(int)((j+arr[i])%k)]=Math.max(dp[i-1][j]+arr[i],dp[i-1][(int)((j+arr[i])%k)]);
            }
        }
        
        //如果小于等于0，说明不能由初始状态转化过来，没有合法方案
        if(dp[n][0]<=0){
            System.out.println(-1);
        } 
        else{
            System.out.println(dp[n][0]);
        }
        
        
    }
    
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$n\ast kn*k$n∗k次，所以时间复杂度为$O(n\ast k)O(n*k)$O(n∗k)。
• 空间复杂度：需要额外大小为$(n+1)\ast k(n+1)*k$(n+1)∗k的dp数组，所以空间复杂度为$O(n\ast k)O(n*k)$O(n∗k)。