首页 > 试题广场 >

模意义下最大子序列和（Easy Version）

[编程题]模意义下最大子序列和（Easy Version）
  • 热度指数：1649 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个含有 n 个正整数的数组 a 以及一个正整数模数 m。你可以任选若干下标递增的元素构成一个子序列（允许选择空序列）。设所选元素之和为 S，求 S \bmod m 的最大可能值。

输入描述:
\hspace{15pt}第一行输入两个整数 n,m\ (1\leqq n\leqq 15,\;1\leqq m\leqq 10^9)。 
\hspace{15pt}第二行输入 n 个整数 a_i\ (1\leqq a_i\leqq 10^9)。


输出描述:
\hspace{15pt}输出一个整数，表示 S \bmod m 的最大值。
示例1

输入

1 1
1

输出

0

说明

可选子序列有 \varnothing（空序列）和 (1)，其元素和分别为 0、1；取模 m=1 后结果均为 0，因此答案为 0。
算法知识视频讲解
添加回答
Java
清浅QAQ头像 清浅QAQ
import java.util.*;

public class Main {
    static int res = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            arr[i] %= m; // 预处理，减少后续计算量
        }
        track(arr, 0, n, m, 0);
        System.out.println(res);
    }
   
    // public static void track(int[] arr, int index, int n, int m, int sum) {
    //     if (index == n) {
    //         res = Math.max(res, sum);
    //         return;
    //     }
    //     // 选择当前元素
    //     track(arr, index + 1, n, m, (sum + arr[index]) % m);
    //     // 不选择当前元素
    //     track(arr, index + 1, n, m, sum);
    // }

    public static void track(int[] arr, int index, int n, int m, int sum) {
        // 每次递归都尝试更新最大值
        res = Math.max(res, sum);

        // 从当前index开始，尝试所有可能的子序列
        for (int i = index; i < n; i++) {
            // 选择arr[i]，并递归处理后面的元素
            track(arr, i + 1, n, m, (sum + arr[i]) % m);
        }
    }
}

发表于 2025-09-22 21:42:00 回复(0)
提交观点

问题信息

dfs
难度：
1条回答 150浏览

热门推荐

相关试题

模意义下最大子序列和（Easy Version）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号