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

C++

jys1221

#include <iostream>

#include <vector>

using namespace std;

using ll = long long;

int n;

ll m, ans = 0;

vector<ll> a;

// dfs(i, sum) 表示当前在处理下标 i，已经累加的模值为 sum

void dfs(int i, ll sum) {

if (i == n) {

ans = max(ans, sum); // sum 本身就是 mod m 后的值

return;

}

// 不选 a[i]

dfs(i + 1, sum);

// 选 a[i]

dfs(i + 1, (sum + a[i] % m) % m);

}

int main() {

cin >> n >> m;

a.resize(n);

for (int i = 0; i < n; i++) {

cin >> a[i];

a[i] %= m;

}

dfs(0, 0);

cout << ans << "\n";

return 0;

}

发表于 2025-07-25 09:50:07 回复(0)

Python3

juo1

n,m=map(int, input().split())
a = list(map(int, input().split()))
a = [x%m for x in a]
max_possible = m-1

def solve(i, cur_val):
    if cur_val==max_possible:
        return cur_val
    if i==n:
        return cur_val
    

    res = (cur_val+a[i])%m
    return max(solve(i+1, cur_val), solve(i+1, res), res)

print(solve(0, 0))

这不该过啊。输入这么多元素。

发表于 2026-03-05 22:36:02 回复(0)

Python 3

绵young

人很少。

n, m = map(int, input().split(" "))
A = [int(_) for _ in input().split(" ")]
# print(n, m, A)

R = [0]

def create(index: int, s: int):
    if s >= R[0]:
        for i in range(index + 1, n):
            s1 = s + A[i]

            if s1 % m > R[0]:
                R[0] = s1 % m
            
            create(i, s1)

for i in range(0, n):
    create(i, A[i])

print(R[0])

发表于 2026-02-19 21:32:16 回复(0)

爱看剧的花生米躺平又起来了

#include <iostream>

#include <vector>

using namespace std;

int max_mod=0;

void mod(int n,int m,int sum,int pos,vector<int>& vi){

if(pos==n)return;

int m1=sum%m;//不选择vi[pos]取模

int m2=(sum+vi[pos])%m;//选择vi[pos]取模

//更新S mod m最大值

max_mod=max_mod>m1?max_mod:m1;

max_mod=max_mod>m2?max_mod:m2;

//递归

mod(n,m,m1,pos+1,vi);

mod(n,m,m2,pos+1,vi);

}

int main() {

int n,m;

cin>>n>>m;

vector<int>vi(n,0);

for(int i=0;i<n;i++){

cin>>vi[i];

}

mod(n,m,0,0,vi);

cout<<max_mod;

}

// 64 位输出请用 printf("%lld")

发表于 2026-02-03 02:30:55 回复(0)

Java

清浅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)

草海桐

package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	k := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &k[i])
	}

	result := 0

	var dfs func(i, sum int)
	dfs = func(i, sum int) {
		if i == n {
			modSum := sum % m
			if modSum > result {
				result = modSum
			}
			return
		}
		// 不选择当前元素
		dfs(i+1, sum)
		// 选择当前元素
		dfs(i+1, sum+k[i])
	}

	dfs(0, 0)
	fmt.Println(result)
}

发表于 2025-09-07 22:40:57 回复(0)

Python3

牛客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)

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

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题