LeetCode 1262中等动态规划
可被三整除的最大和 图解题解
这道题到底在问什么
把规则说清楚:从数组里随便挑一个子集,可以挑也可以不挑,顺序不限,唯一的硬要求是挑出来这些数的和必须能被 3 整除。我们要在所有满足条件的挑法里,找出和最大的那一个。注意空集也算一种合法挑法,它的和是 0,而 0 能被 3 整除,所以答案永远不会是负数,最差也就是 0。提示里数组长度 1 ≤ n ≤ 4 万,每个数 1 ≤ nums[i] ≤ 1 万。
- 输入
- nums = [3,6,5,1,8]
- 输出
- 18(选 3、6、1、8)
- 输入
- nums = [4]
- 输出
- 0(4 不被 3 整除,只能空选)
- 输入
- nums = [1,2,3,4,4]
- 输出
- 12(选 1、3、4、4)
先想最直接的笨办法
整张表填满了,最后一行「余 0」那格是 18,这就是答案。倒推一下它选了谁:全部五个数加起来是 3 加 6 加 5 加 1 加 8 等于 23,23 除以 3 余 2,要把余数清成 0,得舍掉余数为 2 的部分,这里舍掉的正是那个 5,剩下 3、6、1、8 加起来 18,正好能被 3 整除。算法没有真的去枚举舍谁,而是靠三列余数状态自动把这笔账算清了。（动画第 26 步）
最优解：一步一步想明白
- 3只记和对 3 的余数这一个特征,三种余数三个格子。新数余数为 r 时,要凑出余 j 就接到上一行余 (j 减 r) 的那一格,取「不要它」和「接上它」的较大者。
- 4这是一张 DP 表,每一行从左到右三个格子,分别代表选出的和除以 3 余 0、余 1、余 2 时的最大和。最上面一行是起点空集,往下每一行表示又把一个新数纳入考虑。我们从上往下、每行从左往右地填,每填一行就用上一行的结果推出来。最终答案不是某个中间格,而是最后一行最左边那个「余 0」格,因为它代表把所有数都考虑过、且总和能被 3 整除时的最大和。
- 5先填起点这一行,也就是一个数都还没选的状态。什么都不选,和是 0,而 0 除以 3 余 0,所以「余 0」那格填 0,这是一个完全合法的方案。可这时候你没法只靠空集就让和余 1 或者余 2,那两个状态根本还不存在,所以「余 1」「余 2」两格填一个极小的哨兵值,画面上用空集符号表示它们暂时接不上。地基打好,后面每来一个数都基于上一行往下推。
- 6现在把第 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 更划算。
- 7现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 1」的格子 f[0][1] = 空;二是把 3 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[1][1] = 空,两边一样大。
- 8现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 2」的格子 f[0][2] = 空;二是把 3 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[1][2] = 空,两边一样大。
- 9把第 1 个数 3 的三列都算完了,这一行是 3、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
- 10现在把第 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 更划算。
- 11现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 1」的格子 f[1][1] = 空;二是把 6 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[2][1] = 空,两边一样大。
- 12现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 2」的格子 f[1][2] = 空;二是把 6 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[2][2] = 空,两边一样大。
- 13把第 2 个数 6 的三列都算完了,这一行是 9、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
- 14现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 0,前面那部分的余数就得是 1,因为 1 加 2 除以 3 正好余 0。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 0」的格子 f[2][0] = 9;二是把 5 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[3][0] = 9,不要 5 更划算。
- 15现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 1,前面那部分的余数就得是 2,因为 2 加 2 除以 3 正好余 1。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 1」的格子 f[2][1] = 空;二是把 5 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[3][1] = 空,两边一样大。
- 16现在把第 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 更划算。
- 17把第 3 个数 5 的三列都算完了,这一行是 9、空、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
- 18现在把第 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 更划算。
- 19现在把第 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 更划算。
- 20现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 2,前面那部分的余数就得是 1,因为 1 加 1 除以 3 正好余 2。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 2」的格子 f[3][2] = 14;二是把 1 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[4][2] = 14,不要 1 更划算。
- 21把第 4 个数 1 的三列都算完了,这一行是 15、10、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
- 22现在把第 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 更划算。
- 23现在把第 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 更划算。
- 24现在把第 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 更划算。
- 25把第 5 个数 8 的三列都算完了,这一行是 18、22、23。这是最后一行,最左边「余 0」格的 18 就是最终答案。
- 26整张表填满了,最后一行「余 0」那格是 18,这就是答案。倒推一下它选了谁:全部五个数加起来是 3 加 6 加 5 加 1 加 8 等于 23,23 除以 3 余 2,要把余数清成 0,得舍掉余数为 2 的部分,这里舍掉的正是那个 5,剩下 3、6、1、8 加起来 18,正好能被 3 整除。算法没有真的去枚举舍谁,而是靠三列余数状态自动把这笔账算清了。
⚠️ 容易写错的地方
✗ 错：用贪心:先求总和,不被 3 整除就减掉一个最小的数
✓ 对：要按余数分情况:总和余 1 时,减一个最小的余 1 数、或减两个最小的余 2 数,谁损失小用谁;余 2 时反过来。DP 自动覆盖这些情况
只减一个数往往不对。比如总和余 1,但数组里没有余 1 的数,就只能减两个余 2 的数,漏掉这种情况会算错
✗ 错：Java/C++ 里直接写 (j 减 x) 对 3 取模
✓ 对：负数取模在 Java/C++ 会得到负值,必须写成 (j 减 x 对 3 取模 加 3) 再对 3 取模,先掰回 0 到 2
下标算成负数会直接越界或读到错误的格子,Python 没这问题是因为它的取模结果天然非负
✗ 错：把起点的「余 1」「余 2」两格设成 0
✓ 对：它们要设成极小哨兵,只有「余 0」那格才是 0(空集)
空集只能凑出余 0;若把余 1、余 2 也设成 0,等于凭空承认存在和为 0 却余 1 的方案,后面会算出根本不合法的虚高答案
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n = nums.size();
const int inf = 1 << 30;
int f[n + 1][3];
f[0][0] = 0;
f[0][1] = f[0][2] = -inf;
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
for (int j = 0; j < 3; ++j) {
f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x);
}
}
return f[n][0];
}
};Java
import java.util.*;
class Solution {
public int maxSumDivThree(int[] nums) {
int n = nums.length;
final int inf = 1 << 30;
int[][] f = new int[n + 1][3];
f[0][1] = f[0][2] = -inf;
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
for (int j = 0; j < 3; ++j) {
f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x);
}
}
return f[n][0];
}
}复杂度
时间
O(n)
从头到尾扫一遍数组,每个数固定更新 3 个余数状态,3 是常数,所以总时间和数组长度成正比,n 到 4 万也是瞬间
空间
O(n)
按峰值算:参考代码开了一张 (n 加 1) 行乘 3 列的表 f,所以是 O(n)。因为每行只依赖上一行,完全可以只留 3 个滚动变量把空间压到 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 可被三整除的最大和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
状态怎么设,转移是什么?+
设 f[i][j] 为前 i 个数里、选出的和除以 3 余 j 时的最大和。起点 f[0] 等于 [0, 负无穷, 负无穷]。来一个数 x、余数 r,转移是 f[i][j] = max(f[i-1][j], f[i-1][(j 减 r 加 3) 对 3 取模] 加 x),前者不选 x、后者把 x 接到能凑出对应余数的最优和上。答案是 f[n][0],时间 O(n)。
能不能用贪心代替 DP?+
能,但要小心。先求总和 S,如果 S 已经能被 3 整除就直接返回。否则看 S 除以 3 的余数:余 1 时,从「减掉一个最小的余 1 数」和「减掉两个最小的余 2 数」里选损失小的;余 2 时对称处理。贪心更快,但分类讨论容易写错,DP 把这些情况自动包了进去,更稳。
空间能压到 O(1) 吗?+
能。f[i] 只依赖 f[i-1],所以不必开整张二维表,只留 3 个变量代表当前的余 0、余 1、余 2 最大和,边扫边更新即可,空间从 O(n) 降到 O(1)。注意更新时要先用旧的三个值算出新的三个值,别原地覆盖把自己算脏了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 可被三整除的最大和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。