LeetCode 1262. 可被三整除的最大和
目录
题目描述
题意分析
给一个整数数组，从中任意挑出一个子集（元素之间不要求相邻，也不要求保持顺序，每个元素最多用一次），要求这些被选中元素的和能被
3整除，并且在所有满足这个条件的选法里取和最大的那个，输出这个最大和。需要注意选法是「子集」而不是「子数组」，因此不存在连续性约束，也就不能用滑动窗口或前缀和之类依赖位置关系的工具。同时，元素只能选或不选，没有「选几次」的自由度。
约束透露的信号有两条。数组元素都是非负整数，这意味着「多选一个数总是让和变大」，最大化的压力全部来自余数这一个约束条件上；数组长度可到十万级别，说明只能接受线性或接近线性的做法，按子集枚举的 $2^n$ 完全不可行。
边界要留意：空集的和是
0，而0能被3整除，所以答案至少是0，不存在「无解」的情况。数组里全是非3倍数且怎么组合都凑不出3的倍数时，正确输出就是0而不是负数或某种错误码。
解法：按余数维护最大和动态规划
核心思路
枚举子集有 $2^n$ 种选择，但题目最终只关心「和除以 3 的余数」。因此把所有候选按余数压缩成 3 个状态：
dp[r]表示处理完当前前缀后，和模 3 等于r的子集中，能够得到的最大和；不可达状态记为-1。对当前数字
num有两种选择：不选时直接继承原来的dp；选择时从每个可达的旧状态dp[r]出发，得到sum = dp[r] + num，用它更新next[sum % 3]。每轮必须读旧数组、写新数组，因为每个元素只能使用一次。若原地更新，新状态可能在同一轮再次使用
num，就会错误地变成完全背包。正确性可以用归纳说明：初始时只有空集，所以状态为
[0, -1, -1]；转移完整枚举了当前元素选与不选两种情况。对于相同余数，只保留更大的和不会丢失最优解，因为之后无论加入哪些元素，较大的和都会得到相同的新余数且结果不小于较小的和。最终dp[0]即为答案。
解题步骤
- 初始化
dp = [0, -1, -1]，其中dp[0] = 0表示空集。- 遍历每个
num，先复制dp得到next，保留所有「不选」结果。- 枚举余数
r = 0, 1, 2，跳过dp[r] < 0的不可达状态。- 计算
sum = dp[r] + num，更新next[sum % 3]的最大值。- 用
next替换dp，处理下一个数字。- 返回
dp[0]。对
[3, 6, 5, 1, 8]，状态依次为[0,-1,-1] → [3,-1,-1] → [9,-1,-1] → [9,-1,14] → [15,10,14] → [18,22,23]，所以答案为18。
代码实现
class Solution {
public int maxSumDivThree(int[] nums) {
int[] dp = {0, -1, -1};
for (int num : nums) {
int[] next = dp.clone();
for (int r = 0; r < 3; r++) {
if (dp[r] < 0) {
continue;
}
int sum = dp[r] + num;
int remainder = sum % 3;
next[remainder] = Math.max(next[remainder], sum);
}
dp = next;
}
return dp[0];
}
}
func maxSumDivThree(nums []int) int {
dp := [3]int{0, -1, -1}
for _, num := range nums {
next := dp
for r := 0; r < 3; r++ {
if dp[r] < 0 {
continue
}
sum := dp[r] + num
remainder := sum % 3
if sum > next[remainder] {
next[remainder] = sum
}
}
dp = next
}
return dp[0]
}
复杂度分析
- 时间复杂度：$O(n)$。每个元素只转移 3 个余数状态。
- 空间复杂度：$O(1)$。
dp和next的长度固定为 3。
关键点总结
- 状态只保留余数与该余数下的最大和，把指数级子集压缩为 3 个槽位。
- 同余状态中较大的和支配较小的和，这是状态可以合并的依据。
- 快照不是写法偏好，而是保证「每个元素最多选一次」的 0-1 约束。
- 空集使
dp[0]从0开始，因此答案始终存在。
易错点总结
- 直接原地更新
dp：本轮产生的状态可能再次加入同一个num，相当于重复使用元素。- 不跳过
-1状态：不存在的子集会参与转移，产生虚假的候选和。- 只记录是否可达：题目要求最大和，同一余数必须保留数值最大的状态。
- 返回三个状态中的最大值：最大值的余数未必是
0，最终只能返回dp[0]。- 误用连续子数组方法：本题选择的是任意子集，元素位置没有连续性约束。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 368. 最大整除子集 | 中等 | 约束是元素两两整除，需排序后按长度递推并回溯路径 |
| 416. 分割等和子集 | 中等 | 状态按精确和而非余数划分，求可行性不求最大值 |
| 494. 目标和 | 中等 | 元素必须全用且带正负号，统计方案数而非最优值 |
| 523. 连续的子数组和 | 中等 | 限定连续子数组，靠前缀和余数配哈希表定位区间 |
| 974. 和可被 K 整除的子数组 | 中等 | 同样按余数分类，但统计的是连续子数组的个数 |
| 1010. 总持续时间可被 60 整除的歌曲 | 中等 | 只需两元素配对，用余数计数数组直接组合 |
| 1497. 检查数组对是否可以被 k 整除 | 中等 | 要求全部元素两两配对，判定余数计数是否对称 |
| 1590. 使数组和能被 P 整除 | 中等 | 删除的必须是一段连续子数组，求最短删除长度 |