算法分析

优化：

• 1、由于第i层只用到第i - 1层，于j - 1 严格小于j，并且需要用到上一轮的数据，因此需要j从大到小遍历到1，因此可以优化到二维

• 2、贪心：余数相同时取数组较大的数，因此分别将余数是0到k - 1的最大3个数挑出来处理即可，最多挑出3 * 1000个数进行处理

时间复杂度 $O(3k * 3 * k)$

参考文献

蓝桥杯辅导课

Java 代码

import java.util.*;
public class Main{
    static int N = 1010;
    static int INF = 0x3f3f3f3f;
    static int n,m;
    static int[][] f = new int[4][N];
    static LinkedList[] a = new LinkedList[N];
    static int mod(int x,int y)
    {
        return (x % y + y) % y;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i <= m;i ++)
        {
            a[i] = new LinkedList<Integer>();
        }
        for(int i = 1;i <= n;i ++)
        {
            int x = scan.nextInt();
            a[x % m].add(x); 
        }
        for(int i = 0;i <= 3;i ++) Arrays.fill(f[i], -INF);
        f[0][0] = 0;
        for(int i = 0;i <= m;i ++)
        {
            Collections.sort(a[i]);
            Collections.reverse(a[i]);
            //选择前3大
            for(int u = 0;u < Math.min(3, a[i].size());u ++)
            {
                int x = (int) a[i].get(u);
                //从大到小
                for(int j = 3;j >= 1;j --)
                {
                    for(int k = 0;k < m;k ++)
                        f[j][k] = Math.max(f[j][k], f[j - 1][mod(k - x,m)] + x);
                }
            }
        }
        System.out.println(f[3][0]);
    }
}