首页 > 试题广场 >

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

[编程题]模意义下最大子序列和（Easy Version）
  • 热度指数：1730 时间限制：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。
算法知识视频讲解
添加回答
Python3
牛客847294653号头像 牛客847294653号
# 更新答案（考虑当前子序列）
  
n, m = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
ans = 0

def dfs(i, current_sum):
    global ans
    # 更新答案（考虑当前子序列）
    ans = max(ans, current_sum % m)

    # 递归边界
    if i == n:
        return

    # 选择当前元素
    dfs(i + 1, (current_sum + a[i]) % m)

    # 不选择当前元素
    dfs(i + 1, current_sum)

# 从第一个元素开始，初始和为0
dfs(0, 0)
print(ans)

发表于 2025-08-23 13:19:34 回复(0)
提交观点

问题信息

dfs
难度：
1条回答 175浏览

热门推荐

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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