题目
给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。
示例 1：
输入：nums = [3,6,5,1,8] 输出：18 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：
输入：nums = [4] 输出：0 解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：
输入：nums = [1,2,3,4,4] 输出：12 解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
提示：
1 <= nums.length <= 4 * 10^41 <= nums[i] <= 10^4
解题思路
首先，我们要明确一个关于整数求和的数学性质：
若干个数的和的余数 = 若干个数余数的和的余数
这意味着，我们不需要关心具体的数字是 100 还是 10，只关心它们模 3 是 1 还是 2 还是 0。
这就把所有数字分成了三类：
- 余数为 0 的数（如 3, 6, 9）：这些人畜无害，多多益善。不管选多少个，都不会改变总和的余数状态。所以，全部都要选。
- 余数为 1 的数（如 1, 4, 7）。
- 余数为 2 的数（如 2, 5, 8）。
难点就在于如何选择余数为 1 和 2 的数。
逆向思维（做减法）
与其纠结“怎么选才能凑出 3 的倍数”，不如先把所有数都选上，看看总和是多少，然后根据总和的余数，踢掉代价最小的那个“麻烦”。
假设所有数字的总和为 $S$。
1. 如果 $S % 3 == 0$
完美！不需要踢掉任何数，直接返回 $S$。
2. 如果 $S % 3 == 1$
说明现在的和“多出来了 1”。为了让余数变回 0，我们需要从已选的数字中减去一些数，使得减去的这些数的余数之和模 3 等于 1。
我们要让损失最小，所以要找“最小的”组合。方案只有两种：
- 方案 A：删掉 1 个 最小的“余数为 1”的数。（$1 \equiv 1$）
- 方案 B：删掉 2 个 最小的“余数为 2”的数。（$2 + 2 = 4 \equiv 1$）
决策：比较 方案 A 和 方案 B 谁减去的数值更小，就执行谁。
3. 如果 $S % 3 == 2$
说明现在的和“多出来了 2”。我们需要减去一些数，使得减去的这些数的余数之和模 3 等于 2。
同样只有两种方案：
- 方案 A：删掉 1 个 最小的“余数为 2”的数。（$2 \equiv 2$）
- 方案 B：删掉 2 个 最小的“余数为 1”的数。（$1 + 1 = 2$）
决策：比较 方案 A 和 方案 B 谁减去的数值更小，就执行谁。
正向思维（动态规划 DP）
如果我们不善长找这种数学规律，或者题目改成“被 5 整除”、“被 10 整除”，上面的分类讨论就会变得非常复杂。
这时候，我们需要通用的计算机状态机思维。
我们可以把处理数组的过程看作是一个人拿着一个袋子捡石头。袋子里的石头总重模 3 只有三种状态：
- 状态 0：余数为 0
- 状态 1：余数为 1
- 状态 2：余数为 2
我们定义 dp[0], dp[1], dp[2] 分别代表达到该状态时，袋子里能装的最大重量。
状态转移过程
每当我们遇到一个新的数字 num，它都会试图改变当前所有状态的格局。
假设我们现在的状态是 dp（旧状态），来了一个数字 num： 对于每一个旧状态 dp[i]（i 是 0, 1, 2），如果我们把 num 加进去：
- 新的总和 =
dp[i] + num - 新的余数 =
(i + num) % 3
我们需要判断：在这个“新的余数”下，这个“新的总和”是不是比以前记录的更大？ 如果是，就更新它。
具体代码
方法一
func maxSumDivThree(nums []int) int {
// sum: 记录所有数字的累加和
// r1 (Remainder 1): 记录当前遍历过的数字中，能凑出的“余数为1”的最小子集和
// r2 (Remainder 2): 记录当前遍历过的数字中，能凑出的“余数为2”的最小子集和
// 初始化为 100001 是因为题目提示 nums[i] <= 10000，我们需要一个比可能的最大减数更大的值作为“无穷大”哨兵
sum, r1, r2 := 0, 100001, 100001
for _, n := range nums {
sum += n // 贪心策略：先把所有数加起来，最后再考虑减谁
if n%3 == 1 {
// 当前数字 n 余数为 1
// 更新 r2：尝试用“旧的 r1 (余1)”加上“当前的 n (余1)”，凑出余数 2 (1+1=2)
r2 = min(r2, r1 + n)
// 更新 r1：当前的 n 本身就是余数 1，看它是不是比之前的 r1 更小
r1 = min(r1, n)
} else if n%3 == 2 {
// 当前数字 n 余数为 2
// 更新 r1：尝试用“旧的 r2 (余2)”加上“当前的 n (余2)”，凑出余数 1 (2+2=4 -> 余1)
// 注意：这里必须先更新 r1，再更新 r2，防止同一个 n 被使用两次（即脏读）
r1 = min(r1, r2 + n)
// 更新 r2：当前的 n 本身就是余数 2，看它是不是比之前的 r2 更小
r2 = min(r2, n)
}
}
// 此时 sum 已经算出来了，根据 sum 的余数决定要减去多少
if sum%3 == 1 {
// 如果总和余 1，我们需要减去一个“余数为 1 的最小组合” (r1) 来让整体被 3 整除
sum -= r1
} else if sum%3 == 2 {
// 如果总和余 2，我们需要减去一个“余数为 2 的最小组合” (r2)
sum -= r2
}
// 如果 sum%3 == 0，上面的 if 都不会执行，直接返回原 sum
return sum
}
// 辅助函数：Go 1.21 之前并没有内置整数 min，手写一个简单的
func min(a, b int) int {
if a < b {
return a
}
return b
}
方法二
func maxSumDivThree(nums []int) int {
// dp[i] 的含义：
// 在当前遍历过的数字中，选出若干个数字，使得它们的和模 3 余数为 i。
// dp[i] 存储的就是这个“和”的最大值。
// 初始化：
// dp[0] = 0：一个数都不选，和为 0，0 % 3 == 0，这是合法的初始状态。
// dp[1], dp[2] = -1：代表“不可达”。因为刚开始不可能凑出余数为 1 或 2 的和。
dp := []int{0, -1, -1}
for _, v := range nums {
// 创建一个临时数组 temp 用于存储这一轮计算出的新状态。
// 为什么要用 temp？
// 因为在计算过程中，我们需要依赖“上一轮”的 dp 值。
// 如果直接修改 dp 数组，后面的计算可能会用到这一轮刚刚更新过的值（脏读），
// 导致同一个数字 v 被重复累加。这类似于“双缓冲”的概念。
temp := []int{-1, -1, -1}
// 遍历上一轮的三个状态 (余数 j = 0, 1, 2)
for j := range dp {
// 如果 dp[j] == -1，说明上一轮根本凑不出余数 j，既然起点不存在，就无法基于此进行转移，直接跳过。
if dp[j] >= 0 {
// 决策 1：不选当前数字 v
// 那么余数状态不变 (j)，数值也不变 (dp[j])。
// 我们要保留历史最佳值，所以取 max。
temp[j] = max(temp[j], dp[j])
// 决策 2：选中当前数字 v
// 新的余数状态变为：(旧余数 j + 当前数 v) % 3
// 新的总和变为：旧总和 dp[j] + 当前数 v
newRem := (j + v) % 3
temp[newRem] = max(temp[newRem], dp[j] + v)
}
}
// 本轮计算结束，将 temp 的状态同步给 dp，进入下一轮循环
dp = temp
}
// 循环结束后，dp[0] 存储的就是“任意组合后，模 3 余数为 0 的最大和”
// 这正是题目要求的答案。
return dp[0]
}