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

#include <stdio.h>
#include <stdlib.h>

//dfs需要的一些全局变量
long long S = 0;//所选元素和，初始化为0
int res = 0;//最终的最大值，初始化为0

//构建自己的dfs算法
void dfs(int *a, int n, int m, int start){
    //已经扫描完了整个数组，终止递归，返回
    if(start >= n){
        return;
    }
    //选择当前元素加入序列，并判断是否要更新res值
    S += a[start];
    int tmp = S % m;
    if(tmp > res){
        res = tmp;
    }
    //选择当前元素后递归进行下一个元素的判断
    dfs(a, n, m, start + 1);
    
    //撤销选择，不选择当前元素后递归进行下一个元素的判断
    S -= a[start];
    dfs(a, n, m, start + 1);
}

int main() {
    //读取数据
    int n, m;
    scanf("%d %d\n", &n, &m);
    int *a = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++){
        scanf("%d ", a + i);
    }

    //从第一个元素开始递归搜索
    dfs(a, n, m, 0);
    //打印结果
    printf("%d\n", res);
    
    //释放空间
    free(a);
    return 0;
}