题目
LC 1262 可被三整除的最大和：给你一个整数数组
nums，请你找出并返回能被
3 整除的
元素最大和。如果不存在可行解，返回
0。
输入: nums = [3,6,5,1,8]
输出: 18 （3 + 6 + 1 + 8 = 18）
输入: nums = [4]
输出: 0 （4 不能被 3 整除，只能选空集，空集和是 0）
输入: nums = [1,2,3,4,4]
输出: 12 （1 + 3 + 4 + 4 = 12）
先澄清一个最容易被记岔的地方：这题选的是
任意个元素（一个子集），
不是"恰好三个"。示例里
18 = 3 + 6 + 1 + 8 用了四个数 —— 题面里的"三"指的是
被 3 整除，不是"挑三个"。真正的约束只有一条：
所选元素之和 ≡ 0 (mod 3)。
约束里每个
nums[i] 都是
正整数（
1 ≤ nums[i] ≤ 10^4），这条很关键：总和是"能选的最大容器"，我们只需要
从全选里减掉最少的一小撮。全文都建立在这条前提上。
这题有两种都值得会的做法，且互为对照：一次按
余数分组的贪心（
O(n)，全靠"1+1≡2、2+2≡1"），和一台
三格滚动的一维 dp（
O(n)，不依赖正数前提）。下面把它们拆开。
一、核心洞察：先全选，再削掉最小的一撮
因为元素全是正数，
全选的和 S 一定是所有子集和的上界。想让结果被 3 整除，唯一的手段就是
扔掉几个元素，让剩下的和回到
≡ 0。
记
S = sum(nums)、
r = S % 3：
r == 0：S 本身就被 3 整除，全选就是最优 —— 直接返回 S。r == 1：需要扔掉一小撮，其和 ≡ 1 (mod 3)。r == 2：需要扔掉一小撮，其和 ≡ 2 (mod 3)。
再按每个数对 3 的余数把它们分成三桶：
m0（余 0）、
m1（余 1）、
m2（余 2），都
升序排好。余 0 的元素永远不用扔（扔了纯粹亏），所以只在
m1、
m2 里做文章：
r == 1：要么扔一个 m1 里的数（它本身 ≡ 1），要么扔两个 m2 里的数（2 + 2 = 4 ≡ 1）。取两者中代价更小的那个。r == 2：要么扔一个 m2 里的数（≡ 2），要么扔两个 m1 里的数（1 + 1 = 2 ≡ 2）。同样取代价更小的。
答案就是
S - 代价；如果两种方案都不存在（桶里凑不齐），说明无解，返回
0。
def maxSumDivThree(nums):
total = sum(nums)
r = total % 3
if r == 0:
return total
m1 = sorted(x for x in nums if x % 3 == 1)
m2 = sorted(x for x in nums if x % 3 == 2)
def two(bucket):
return bucket[0] + bucket[1] if len(bucket) >= 2 else float('inf')
if r == 1: # 削掉一个 1，或两个 2
drop = min(m1[0] if m1 else float('inf'), two(m2))
else: # r == 2：削掉一个 2，或两个 1
drop = min(m2[0] if m2 else float('inf'), two(m1))
return 0 if drop == float('inf') else total - drop
两处细节决定成败：
- 桶必须升序，且只取"最小的那几个"。既然所有数都正，扔得越少越好，所以候选永远是每个桶里最小的一个 / 两个 —— 排序后取前两个即可，后面的数根本轮不到。
two(bucket) 要在长度不够时给 ∞，而不是给 0。给 0 等于凭空声称"能白白削掉两个数"，min 会立刻选中一条不存在的路。
二、为什么删除只需看"一个 r 或两个 3−r"
上一节直接给了结论，这里补一刀证明 —— 它其实是全文最值钱的一句。
设要扔的集合和为
d，且
d ≡ r (mod 3)（
r∈{1,2}）。把
d 拆成若干元素，只看
每个元素对 3 的余数，那么：
余 1 贡献 1、余 2 贡献 2，加总后模 3 要为
r。
- 一个元素：余数直接是
r，即"一个 m_r 里的数"。
- 两个元素：
1+1≡2、2+2≡1、1+2≡0。想要 r，只能是两个同为 3−r 的数（(3−r)+(3−r) ≡ −2r ≡ r）。混合 1 和 2 得到 0，白扔。
- 三个及以上：要么出现"三个同类"（
3×余数 ≡ 0，对修正余数毫无帮助，纯亏），要么可归约成上面更小的组合 —— 因为元素都是正数，多扔一个必然让和更小，绝不会更优。
于是"最小代价"必然落在两种形状之一：
最小的一个 m_r，或
最小的两个 m_{3−r}。三种及以上的组合永远被这两种支配。这就是为什么代码里只有两个候选，却已经完全正确。
一句话记住骨架：
r == 0 直接返回 S；否则答案是 S − min(一个 m_r, 两个 m_{3−r})，凑不出就返回 0。
三、动画怎么看
动画一（
algo-viz--lc1262）：按余数分组的贪心。最上面是
nums 原数组，每个格子标出数值和它对 3 的余数；中间三列
m0 / m1 / m2 把元素归位（升序），当前要看的那一桶描绿；下面是两张候选卡片 —— "削一个
m_r" 和 "削两个
m_{3−r}" —— 各自现场算出代价，胜者描金；底栏给出
S、
r 和最终
S − 代价。盯住三件事：
S % 3 == 0 时两张卡片直接收起、答案就是 S；
候选只取每桶最小的一个/两个（桶里更靠后的数整场都不亮）；以及
两张卡片都可能因凑不齐而显示 ∞。
动画二（
algo-viz--lc1262dp）：三格滚动的取模 dp。上面一行是
dp[0] / dp[1] / dp[2] 三个状态（
dp[j] = 当前前缀里，和 ≡
j 的最大和，初值
[0, −∞, −∞]），旁边是正在处理的
nums[i]；每处理一个数就发一帧，把"从哪个旧状态、加上这个数、落到哪个新状态"用弧线画出来，更新的格子描金。最下面是横幅
dp[(j + x%3)%3] = max(dp[...], dp[j] + x) 的现场取值。盯住两点：
每个数只在这一帧里被"用一次"（先拷贝一份
newdp 再写，绝不原地改 —— 否则同一个数会被用两遍）；以及
−∞ 会一路沉底，只有真正可达的余数状态才会被点亮。
两个动画分工明确：动画一是
贪心（一趟求和 + 按余数分桶，靠正数前提），动画二是
dp（三格状态滚动，不依赖正负）。同一组数据、同一个答案
18。
四、完整推演表
动画一：
nums = [3, 6, 5, 1, 8]（与动画默认一致）。
被扔掉的是
5，保留
3 + 6 + 1 + 8 = 18，恰好被 3 整除。注意候选 B 凑不齐（
m1 里只有
1 一个元素），显示
∞ 被候选 A 完胜。
动画二：同一组数据，看三格 dp 怎么滚。
最终
dp = [18, 22, 23]，返回
dp[0] = 18。中间那几格的
22、
23 是"和更大、但余数不是 0"的中间产物 —— 它们被留着，正是为了后面还能被别的数"救回来"。最后一步
x = 8 尤其能说明这一点：
dp[2] = max(14, 15 + 8) = 23、
dp[1] = max(10, 14 + 8) = 22、
dp[0] = max(15, 10 + 8) = 18 —— 三个状态各由一条不同的最优路径刷新，谁的"旧余数 + 新元素余数"恰好落到自己头上，谁就更新。
五、另一条路：三格滚动的取模 dp
贪心依赖"元素全为正"。一旦题目允许
负数，
S − 最小删除 的框架就塌了 —— 此时用 dp 更稳，且它照样是
O(n)。
定义：
dp[j] = 当前已扫描的元素里，子集和 ≡ j (mod 3) 的最大和（j ∈ {0, 1, 2}）；- 初值
dp = [0, −∞, −∞]：空集的和是 0，余 0；余 1、余 2 暂时不可达，给 −∞。
对每个
x，先
拷贝一份 dp 当旧值，再枚举旧状态
j：
newdp[(j + x % 3) % 3] = max( newdp[...], dp[j] + x ) （dp[j] != −∞）
def maxSumDivThree(nums):
NEG = float('-inf')
dp = [0, NEG, NEG] # dp[j] = 和 ≡ j (mod 3) 的最大和
for x in nums:
old = dp[:] # 先快照，避免同一个 x 被用两次
rem = x % 3
for j in range(3):
if old[j] == NEG:
continue
k = (j + rem) % 3
dp[k] = max(dp[k], old[j] + x)
return dp[0]
三个细节：
- 先快照
old = dp[:]，再往 dp 写。这是 0-1 背包的"每件只用一次"：若原地更新，枚举到后面可能读到刚被同一个 x 写过的新值，等于把这个数用两次（和"完全背包"的坑同源，只是这里方向反了）。
−∞ 而非 0 当不可达。用 0 会让 dp[1]、dp[2] 一开始就"可达且和为 0"，max 大面积选错。- 只用三个状态。余数只有 3 种，所以状态压缩到 3 格，空间
O(1)，和贪心一样。
它和贪心的关系：dp 是
通用解（对负数也成立），贪心是
正数特化（更快、更好写，但前提不能破）。面试里先讲贪心的思路，再补一句"若允许负数则改用取模 dp"，是最稳的答法。
六、同族题：974 / 1590 / 1497 / 1018 / 2435
1262 属于"
把和扔进余数世界"这一族。同一副骨架换个问法，就是一条题链：
- LC 974 和可被 K 整除的子数组：前缀和 + 同余。
(pre[i] − pre[j]) % K == 0 等价于 pre[i] ≡ pre[j] (mod K)，数有多少对同余前缀即可（哈希计数）。
- LC 1590 使数组和能被 P 整除的最短子数组：先求总余数
r，再找最短的一段子数组其和 ≡ r (mod p)（前缀和 + 哈希存最早出现位置）。1262 是"删最少元素"，1590 是"删最短连续段"。
- LC 1497 检查数组对是否可以被 k 整除：两两配对，按余数互补（余
0 配余 0，余 r 配余 k−r）—— 和 1262 的"余数分组"是同一个动作。
- LC 1018 可被 5 整除的二进制前缀：逐位维护前缀对 5 的余数，
pre = (pre * 2 + bit) % 5，本质是"和（这里是二进制移位和）取模"。
- LC 2435 矩阵中和能被 K 整除的路径：在网格上做"路径和的余数"dp，
dp[i][j][r] 计数 —— 1262 的一维三格 dp 是它在网格上的推广。
把它们排成一列看：
只要问题里出现"能被 K 整除"，就先想"把和压成一个余数"；剩下的就是在余数状态上做计数（974）、找最短段（1590）、互补配对（1497）、逐位递推（1018）或网格推广（2435）。1262 只是这条轴上"求最大和"的那一个点。
七、Java 版
class Solution {
// LC 1262：余数分组的贪心 —— 与推演表逐帧一致
public int maxSumDivThree(int[] nums) {
int total = 0;
final int INF = Integer.MAX_VALUE / 2; // 别用 MAX_VALUE，相加会溢出
int one1 = INF, one2 = INF; // 最小的两个余 1
int two1 = INF, two2 = INF; // 最小的两个余 2
for (int x : nums) {
total += x;
if (x % 3 == 1) {
if (x < one1) { one2 = one1; one1 = x; }
else if (x < one2) { one2 = x; }
} else if (x % 3 == 2) {
if (x < two1) { two2 = two1; two1 = x; }
else if (x < two2) { two2 = x; }
}
}
int r = total % 3;
if (r == 0) return total;
long drop;
if (r == 1) drop = Math.min(one1, (long) two1 + two2); // 削一个 1，或两个 2
else drop = Math.min(two1, (long) one1 + one2); // 削一个 2，或两个 1
return drop >= INF ? 0 : total - (int) drop;
}
}
class Solution {
// LC 1262：三格滚动的取模 dp —— 允许负数，同样 O(n)
public int maxSumDivThree(int[] nums) {
final int NEG = Integer.MIN_VALUE / 2;
int[] dp = {0, NEG, NEG}; // dp[j] = 和 ≡ j (mod 3) 的最大和
for (int x : nums) {
int[] old = dp.clone(); // 每件只用一次：先快照
for (int j = 0; j < 3; j++) {
if (old[j] == NEG) continue;
int k = (j + Math.floorMod(x, 3)) % 3;
dp[k] = Math.max(dp[k], old[j] + x);
}
}
return dp[0];
}
}
两处 Java 专属的坑：
哨兵要用 Integer.MAX_VALUE / 2（或 MIN_VALUE / 2），
MAX_VALUE + 1 会溢出成负数；
x % 3 在
x 为负时是负数，取余数用
Math.floorMod(x, 3) 更稳。另外求和
total 与
one1 + one2 都可能超过
int（
4×10^4 个
10^4），必要时用
long。
八、边界情况
r == 0：全选即最优，直接返回 S，根本不用看桶；- 只有一个元素：
[4] → S = 4、r = 1，m1 = [4] 但只有一个、m2 为空、候选 B 也凑不齐 → drop = 4 → 返回 0（选空集）；
- 凑不齐删除项：
[1] → S = 1、r = 1，m1 = [1]（削它得 0）、两个 m2 不存在 → 返回 0；
- 答案可能小于总和很多：
[1,1,1] → S = 3、r = 0 → 直接返回 3；[2,2,2] → S = 6、r = 0 → 6；
m1 或 m2 为空：贪心里对应候选必须当 ∞ 处理，别让"取两个"越界；0 元素：余 0、不影响余数，[0, 3] → 返回 3；- 空的
nums：题面保证非空，但语义上返回 0（空集）；
- 重复元素：
[1,1,1,1] → S = 4、r = 1，削一个 1 → 3；m2 为空。排序后取前两个的逻辑对重复值天然正确。
九、复杂度
n 是数组长度。贪心的瓶颈只在"取每个桶最小的两个"上：若真的去
sort，就是
O(n log n)；但用一个"维护最小、次小"的滚动写法（Java 版），一趟扫描即可降到
O(n)、空间
O(1)。dp 天生
O(n) /
O(1)（状态只有 3 个）。
两者时间同级，区别在于贪心依赖"元素非负"这条前提，dp 不依赖。
十、常见坑
- 把"被 3 整除"当成"选三个数"：题面选任意个，
18 = 3 + 6 + 1 + 8 就是四个数。写错这一条，整题全错。
- 只考虑"削一个"，漏掉"削两个"：
r == 1 时，m1 可能没有元素，但 m2 里有两个 —— 只写一个候选会漏解。
two() 长度不足时返回 0：等于宣称能白削两个数，min 立刻选错。必须给 ∞。- 桶没排序就取前两个：取到的不是"最小的两个"，代价不是最小，答案偏小。要么
sort，要么像 Java 版那样维护最小、次小。
- 忘了
r == 0 的短路：虽然返回 S 也未必错，但会把两张候选卡片算得莫名其妙（无解时甚至返回 0）—— 先判 r == 0 最干净。
- 候选凑不齐时返回负数：无解要返回
0（空集），不是 S − ∞ 或某个负值。
- dp 里原地更新：不先拷贝
old，同一个数会被用两次，答案虚高。这是 0-1 背包的经典坑。
- dp 用
0 初始化 dp[1]/dp[2]：等于宣布余 1、余 2 一开始就可达且和为 0，max 大面积出错。用 −∞。
- Java 用
Integer.MAX_VALUE 当 ∞：MAX_VALUE + 1 溢出成负数，min 选错。用 MAX_VALUE / 2，并注意 total 的 long 化。
十一、面试怎么答
第一段 · 贪心：因为元素都为正，全选的和
S 是上界，只需"扔掉最小的一撮"让余数归零。按余数分三桶，
r == 1 时削"一个余 1"或"两个余 2"，
r == 2 时削"一个余 2"或"两个余 1"，取代价小者；
r == 0 直接返回
S。
说清为什么只需这两种形状 —— 这是区分度所在。
第二段 · 补 dp 视角：若元素允许负数，"全选再削"的框架失效，改用三格滚动 dp：
dp[j] = 和 ≡
j (mod 3) 的最大和，初值
[0, −∞, −∞]，每个数先快照再
max 转移。
O(n) /
O(1)，不依赖正负。
第三段 · 一句话收束：
r == 0 返回
S，否则
S − min(一个 m_r, 两个 m_{3−r})；本质是
把和压进余数世界。
追问连跳：
- 要
数有多少个可被 K 整除的子数组 → LC 974，前缀和 + 同余哈希；
- 要
删最短的一段使和被 P 整除 → LC 1590，前缀和 + 最早位置哈希；
- 变成
两两配对能否整除 → LC 1497，余数互补；
- 搬到
网格上 → LC 2435，
dp[i][j][r] 计数。
一句话收尾："可被三整除的最大和只有一台机器 ——
按余数分组，从全选里削掉最小的一撮；贪心是它的正数特化，取模 dp 是它对负数也成立的通用版。"
结语
1262 的全部难度浓缩在一句结论里：
r == 0 返回
S，否则
S − min(一个 m_r, 两个 m_{3−r})。之所以只需要两种形状，是因为余数世界里
1+1≡2、
2+2≡1、
1+2≡0 —— 三个同类抵消、一混合就白扔，多削只会更亏。把这条想透，代码就只有十行；而三格滚动的取模 dp 则提醒我们：一旦"元素全为正"的前提破了，就该换一台不依赖它的机器。
下一篇见。