题解 | 小红取数

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }

        long[] dp = new long[k];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;

        for (long num : a) {
            long[] temp = dp.clone();
            for (int r = 0; r < k; r++) {
                if (temp[r] == Long.MIN_VALUE) {
                    continue;
                }
                int newR = (int) ((r + num) % k);
                if (dp[newR] < temp[r] + num) {
                    dp[newR] = temp[r] + num;
                }
            }
        }

        if (dp[0] > 0) {
            System.out.println(dp[0]);
        } else {
            System.out.println(-1);
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入的数组长度n，整数k以及数组a。
2. 动态规划数组初始化：dp数组初始化为负无穷，表示不可达状态，只有dp[0]设为0，表示初始和为0。
3. 遍历每个数：对于每个数，克隆当前dp数组以避免覆盖当前状态，遍历所有可能的余数，更新选取该数后的新余数的最大和。
4. 结果判断：处理完所有数后，检查dp[0]的值。如果大于0，输出该值，否则输出-1。