JavaScript如何实现查找数组元素可被k整除的最大可能和

现有代码的问题 #

你目前写的代码存在两个核心错误：

1. 逻辑颠倒：所有元素的总和本身就是最大的可能和，如果它能被k整除，直接返回即可，你反而在sum % k == 0的时候减去元素，只会得到更小的结果
2. 没有覆盖所有组合：仅按顺序遍历减元素，无法匹配不同下标的元素组合场景

入门级解法：暴力枚举所有子集（适合理解组合逻辑） #

你提到的「覆盖所有元素组合」本质就是枚举数组的所有子集，每个元素有「选」和「不选」两种状态，可以用位运算很方便的实现：

• 用数字的二进制位代表对应下标的元素是否选中，比如二进制第0位为1代表选下标0的元素，第3位为1代表选下标3的元素，刚好可以覆盖你提到的跨下标组合场景
• 遍历所有可能的子集，计算每个子集的和，校验是否能被k整除，记录最大的符合要求的和即可

示例代码：

function luckyCandies(prizes, k) {
  let maxSum = 0;
  const n = prizes.length;
  // 枚举所有非空子集：i从1到2^n - 1
  for (let i = 1; i < (1 << n); i++) {
    let currentSum = 0;
    for (let j = 0; j < n; j++) {
      // 检查第j位是否为1，是则累加对应元素
      if (i & (1 << j)) {
        currentSum += prizes[j];
      }
    }
    // 校验整除条件，更新最大值
    if (currentSum % k === 0 && currentSum > maxSum) {
      maxSum = currentSum;
    }
  }
  return maxSum;
}

注意：该方法仅适合数组长度小于20的场景，数组过长时枚举所有子集的时间会指数级增长

高效解法：动态规划（适合长数组场景） #

如果数组长度较大，可以用动态规划来优化时间复杂度，思路如下：

• 定义dp[i]为「余数为i的最大和」，初始时dp[0] = 0，其余值设为负无穷代表不可达
• 遍历每个数字，计算它除以k的余数r，更新dp数组：对于每个已有余数j，选中当前数字后的新余数为(j + r) % k，更新对应余数的最大和
• 遍历完成后，dp[0]就是能被k整除的最大和

示例代码：

function luckyCandies(prizes, k) {
  const dp = new Array(k).fill(-Infinity);
  dp[0] = 0;
  for (const num of prizes) {
    const r = num % k;
    // 复制旧dp状态，避免更新时覆盖原始值
    const oldDp = [...dp];
    for (let j = 0; j < k; j++) {
      if (oldDp[j] !== -Infinity) {
        const newR = (j + r) % k;
        dp[newR] = Math.max(dp[newR], oldDp[j] + num);
      }
    }
  }
  // 无符合条件的组合时返回0
  return dp[0] > 0 ? dp[0] : 0;
}

该方法的时间复杂度为O(n*k)，哪怕数组长度过万也可以快速运行。

内容的提问来源于stack exchange，提问作者Jonathan Joseph