题目描述
思路解析
一句话答案：LeetCode 1262 可被三整除的最大和：按和除以 3 的余数分三个桶做动态规划，f[j] 记余数为 j 的最大和，每个数把三桶各更新一次取较大者，答案是余 0 桶。一趟线性扫，时间 O(n)、空间 O(1)。
可被三整除的最大和，到底在挑什么样的子集
给一个整数数组 nums，挑若干个数（可以一个不挑），要挑出的和能被 3 整除且最大。空集也合法（和 0），答案最差 0、永不为负。以 [3,6,5,1,8] 为例，答案 18，挑出 3、6、1、8。
n 个数每个挑或不挑，2ⁿ 种子集为什么试不完
n 个数各挑或不挑，全摆出来就是 2ⁿ 种子集，n 到 4 万逐个验根本跑不完。有用的信息只有一个：这堆数的和除以 3 的余数（取模，除以 3 只可能余 0、1、2）。和本身可以很大，但余数相同的两堆，对后面能不能凑成被 3 整除的影响完全一样。
只记余数不记具体的和，三个桶怎么就够了
既然只有余数要紧，就用动态规划（把『和除以 3 余 j 时的最大和』算一次存下、后面直接取）记账。定义 f[j] 为「和除以 3 余 j 时的最大和」，f[j] 就叫状态（某局面下的最优结果）。余数只有 0、1、2，故永远三个桶 f[0]、f[1]、f[2]。起手没挑数，和 0、余 0，f[0]=0；余 1、余 2 此刻凑不出来，填极小哨兵（比任何真实和都小的「不可能」标记）。
来一个新数，三个桶各自该接上一行的哪一列
每来一个新数 x，先看它除以 3 余几，记作 r。要让新余数落在 j，前面那部分就得余 (j-r) 调正到 0~2 的那个数，因为 (j-r)+r 除以 3 正好余 j。于是每个桶 f[j] 有两条来路：不挑 x 保留旧的 f[j]；或把 x 接到旧的 f[(j-r)] 桶上加个 x，两者取较大者，这一步叫状态转移（由旧状态推出新状态的规则）。注意接的常不是同名桶：余 2 的数想凑余 0，接的是旧的余 1 桶。全部处理完答案在 f[0]，即总和整除时的最大和。
拿 [3,6,5,1,8] 把三个桶从头滚一遍
起手三桶 [0, 极小, 极小]（对应余 0、1、2）。数 3（余 0）接旧余 0：0+3=3。数 6（余 0）：3+6=9。数 5（余 2）凑余 2 接旧余 0：9+5=14。数 1（余 1）：凑余 0 接旧余 2 得 max(9, 14+1)=15，凑余 1 接旧余 0 得 10，得 [15, 10, 14]。数 8（余 2）：凑余 0 接旧余 1 得 max(15, 10+8)=18，凑余 1 得 22，凑余 2 得 23，得 [18, 22, 23]。答案取 f[0]=18，即题面所求；相当于从总和 23（余 2）舍掉余 2 的 5，剩 3、6、1、8 恰好 18。
哨兵图省事写成 0，答案为什么会凭空冒出个不合法的和
余 1、余 2 桶的初值一旦图省事写成 0，后面就会接出根本不存在的方案，它俩必须是极小哨兵。Java、C++ 里 (j-x) 取模会得到负数、当下标就越界，得写成 ((j-x)%3+3)%3 掰回 0~2。还有答案取 f[0]，别看 f[2] 常更大就返回它——它的和余 2、不合法。
从头扫一遍数组，每个数固定更新 3 个桶，总时间与数组长度成正比，记作 O(n)（大 O 记号，规模变大时运算量的增长量级）。参考代码开 (n+1)×3 的表，空间 O(n)；每行只依赖上一行，用三个变量滚动覆盖能压到 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
只记和对 3 的余数这一个特征,三种余数三个格子。新数余数为 r 时,要凑出余 j 就接到上一行余 (j 减 r) 的那一格,取「不要它」和「接上它」的较大者。
总览 · 三列对应三种余数：这是一张 DP 表,每一行从左到右三个格子,分别代表选出的和除以 3 余 0、余 1、余 2 时的最大和。最上面一行是起点空集,往下每一行表示又把一个新数纳入考虑。我们从上往下、每行从左往右地填,每填一行就用上一行的结果推出来。最终答案不是某个中间格,而是最后一行最左边那个「余 0」格,因为它代表把所有数都考虑过、且总和能被 3 整除时的最大和。
起点 · 空集打地基：先填起点这一行,也就是一个数都还没选的状态。什么都不选,和是 0,而 0 除以 3 余 0,所以「余 0」那格填 0,这是一个完全合法的方案。可这时候你没法只靠空集就让和余 1 或者余 2,那两个状态根本还不存在,所以「余 1」「余 2」两格填一个极小的哨兵值,画面上用空集符号表示它们暂时接不上。地基打好,后面每来一个数都基于上一行往下推。
第 1 个数 3 · 填「余 0」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 0,前面那部分的余数就得是 0,因为 0 加 0 除以 3 正好余 0。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 0」的格子 f[0][0] = 0;二是把 3 接到上一行「余 0」那个最优和上,0 加 3 等于 3。两者取大,f[1][0] = 3,接上 3 更划算。
第 1 个数 3 · 填「余 1」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 1」的格子 f[0][1] = 空;二是把 3 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[1][1] = 空,两边一样大。
第 1 个数 3 · 填「余 2」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 2」的格子 f[0][2] = 空;二是把 3 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[1][2] = 空,两边一样大。
第 1 个数 3 · 这一行填完：把第 1 个数 3 的三列都算完了,这一行是 3、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 2 个数 6 · 填「余 0」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 0,前面那部分的余数就得是 0,因为 0 加 0 除以 3 正好余 0。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 0」的格子 f[1][0] = 3;二是把 6 接到上一行「余 0」那个最优和上,3 加 6 等于 9。两者取大,f[2][0] = 9,接上 6 更划算。
第 2 个数 6 · 填「余 1」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 1」的格子 f[1][1] = 空;二是把 6 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[2][1] = 空,两边一样大。
第 2 个数 6 · 填「余 2」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 2」的格子 f[1][2] = 空;二是把 6 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[2][2] = 空,两边一样大。
第 2 个数 6 · 这一行填完：把第 2 个数 6 的三列都算完了,这一行是 9、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 3 个数 5 · 填「余 0」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 0,前面那部分的余数就得是 1,因为 1 加 2 除以 3 正好余 0。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 0」的格子 f[2][0] = 9;二是把 5 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[3][0] = 9,不要 5 更划算。
第 3 个数 5 · 填「余 1」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 1,前面那部分的余数就得是 2,因为 2 加 2 除以 3 正好余 1。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 1」的格子 f[2][1] = 空;二是把 5 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[3][1] = 空,两边一样大。
第 3 个数 5 · 填「余 2」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 2,前面那部分的余数就得是 0,因为 0 加 2 除以 3 正好余 2。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 2」的格子 f[2][2] = 空;二是把 5 接到上一行「余 0」那个最优和上,9 加 5 等于 14。两者取大,f[3][2] = 14,接上 5 更划算。
第 3 个数 5 · 这一行填完：把第 3 个数 5 的三列都算完了,这一行是 9、空、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 4 个数 1 · 填「余 0」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 0,前面那部分的余数就得是 2,因为 2 加 1 除以 3 正好余 0。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 0」的格子 f[3][0] = 9;二是把 1 接到上一行「余 2」那个最优和上,14 加 1 等于 15。两者取大,f[4][0] = 15,接上 1 更划算。
第 4 个数 1 · 填「余 1」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 1,前面那部分的余数就得是 0,因为 0 加 1 除以 3 正好余 1。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 1」的格子 f[3][1] = 空;二是把 1 接到上一行「余 0」那个最优和上,9 加 1 等于 10。两者取大,f[4][1] = 10,接上 1 更划算。
第 4 个数 1 · 填「余 2」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 2,前面那部分的余数就得是 1,因为 1 加 1 除以 3 正好余 2。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 2」的格子 f[3][2] = 14;二是把 1 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[4][2] = 14,不要 1 更划算。
第 4 个数 1 · 这一行填完：把第 4 个数 1 的三列都算完了,这一行是 15、10、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 5 个数 8 · 填「余 0」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 0,前面那部分的余数就得是 1,因为 1 加 2 除以 3 正好余 0。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 0」的格子 f[4][0] = 15;二是把 8 接到上一行「余 1」那个最优和上,10 加 8 等于 18。两者取大,f[5][0] = 18,接上 8 更划算。
第 5 个数 8 · 填「余 1」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 1,前面那部分的余数就得是 2,因为 2 加 2 除以 3 正好余 1。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 1」的格子 f[4][1] = 10;二是把 8 接到上一行「余 2」那个最优和上,14 加 8 等于 22。两者取大,f[5][1] = 22,接上 8 更划算。
第 5 个数 8 · 填「余 2」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 2,前面那部分的余数就得是 0,因为 0 加 2 除以 3 正好余 2。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 2」的格子 f[4][2] = 14;二是把 8 接到上一行「余 0」那个最优和上,15 加 8 等于 23。两者取大,f[5][2] = 23,接上 8 更划算。
第 5 个数 8 · 这一行填完：把第 5 个数 8 的三列都算完了,这一行是 18、22、23。这是最后一行,最左边「余 0」格的 18 就是最终答案。
完成 · 答案 18：整张表填满了,最后一行「余 0」那格是 18,这就是答案。倒推一下它选了谁:全部五个数加起来是 3 加 6 加 5 加 1 加 8 等于 23,23 除以 3 余 2,要把余数清成 0,得舍掉余数为 2 的部分,这里舍掉的正是那个 5,剩下 3、6、1、8 加起来 18,正好能被 3 整除。算法没有真的去枚举舍谁,而是靠三列余数状态自动把这笔账算清了。
三个边界都能手验:单数凑不出时返回 0、总和余 2 时舍最小余 2 数、总和本就整除时全选。
面试三连:f[i][j] 按余数设状态加转移;可用贪心但要按余数分类讨论且可能减两个数;空间能滚动到 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxSumDivThree(self, nums: List[int]) -> int: n = len(nums) f = [[-inf] * 3 for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(nums, 1): for j in range(3): f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x) return f[n][0]复杂度
- 时间：O(n)，从头到尾扫一遍数组,每个数固定更新 3 个余数状态,3 是常数,所以总时间和数组长度成正比,n 到 4 万也是瞬间
- 空间：O(n)，按峰值算:参考代码开了一张 (n 加 1) 行乘 3 列的表 f,所以是 O(n)。因为每行只依赖上一行,完全可以只留 3 个滚动变量把空间压到 O(1)
易错点
面试追问把动画讲成自己的话
追问状态怎么设,转移是什么?
追问能不能用贪心代替 DP?
追问空间能压到 O(1) 吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计全 1 子矩形
LeetCode 1504 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题