题目描述

相关题解:
作者： Mamba_ZJP
链接： https://www.acwing.com/solution/content/21422/

[((k - a[i]) % m + m) % m] 是为了防止 k - a[i] 为负数

算法1

import java.util.*;

public class Main {
    static final int N = 10000;
    static final int M = 1010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[N];
        int[][][] f = new int[N][5][M];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        for (int[][] layer2 : f) {
            for (int[] layer1 : layer2) {
                for (int j = 0; j < layer1.length; j++) {
                    layer1[j] = Integer.MIN_VALUE;
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            f[i][0][0] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 0; k < m; k++) {
                    f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - 1][((k - a[i]) % m + m) % m] + a[i]);
                }
            }
        }

        int ans = -1;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, f[i][3][0]);
        }

        System.out.println(ans);
    }
}