描述

一个数组，取一些数使得取的数之和尽可能大，但要求这个和必须是 的倍数。

输入描述：
第一行输入两个正整数 n 和 k
第二行输入 n 个正整数

输出描述：
如果没有合法方案，输出 -1。
否则输出最大的和。

示例1

输入：
5 5
4 8 2 9 1
输出：
20

说明：
取后四个数即可

思路

问题要求在一个数组中，选取一定数字组配成能够被k整除最大的和，若采取基本做法，那么需要计算每个数字是否加入到Sum中，并求和，复杂度为指数级别

采取动态规划dp[n][i]=k 表示前n个数字中选取一定量数字，使得sum%k=i 最大的和为k

递推方程

对于第n个数字，求解dp[n][i]

• 不加入到序列中 那么dp[n][i]=dp[n-1][i]
• 加入到序列中，那么arr[n]+dp[n-1][(k+j-arr[n]%k)%k]

其中(k+j-arr[n]%k)%k 累加上arr[n] 可以使得sum可以除k余j

在1、2中取较大值即可

代码

易错点

由于需要 i-1 所以可以增加辅助一列，同时初始化所有的元素 为足够小的负数，不能初始化为0 因为为0 那么dp[i][j]可以始终不断增大（dp[i-1][(k+j-arr[i]%k)%k]+arr[i]），但是实际情况可能不能组配出对应余数

最终的判定即为对应dp是否>0

节约内存做法：滚动数组

由于每次仅仅会使用到dp[i-1][] 因此采取滚动数组做法

由于无法使用一组一维数组完成滚动，因而采取 2个一维数组进行滚动
采取now next交替使用，工作数组覆盖历史数组