---

1262. 可被三整除的最大和

• 标签：贪心、数组、动态规划、排序
• 难度：中等

题目链接

• 1262. 可被三整除的最大和 - 力扣

题目大意

描述：给你一个整数数组 $nums$，你需要从数组中选出一些数（可以不选），使得这些数的和能被 $3$ 整除。

要求：找出并返回能被三整除的最大和。

说明：

• $1 \le nums.length \le 4 \times 10^{4}$。
• $1 \le nums[i] \le 10^{4}$。

示例：

• 示例 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：动态规划

1. 阶段划分

依次处理数组中的每个数字，每来一个数字，我们都决定是否选取它。这种「选或不选」的决策天然适合动态规划。

2. 定义状态

定义 $dp[r]$ 表示当前已经处理过的数字中，能够得到的、模 $3$ 的余数为 $r$ 的最大和，其中 $r = 0, 1, 2$。

例如 $dp[0]$ 表示当前能得到的模 $3$ 余 $0$ 的最大和，$dp[1]$ 表示模 $3$ 余 $1$ 的最大和，$dp[2]$ 表示模 $3$ 余 $2$ 的最大和。

3. 状态转移方程

对于当前数字 $num$，记 $r = num \% 3$。我们需要考虑：把 $num$ 加到已有的各个余数状态上，会得到新的余数。

对于每个已有状态 $i$（$i = 0, 1, 2$），如果 $dp[i] \neq -1$（表示该状态可达）：

• 新余数 = $(i + r) \% 3$
• 新和 = $dp[i] + num$
• 更新 $new\_dp[(i + r) \% 3] = \max(new\_dp[(i + r) \% 3], dp[i] + num)$

同时，不选 $num$ 的情况也需要保留，所以 $new\_dp[i]$ 至少等于 $dp[i]$。

4. 初始条件

不选取任何数时，和为 $0$，模 $3$ 余 $0$，所以 $dp[0] = 0$。
$dp[1]$ 和 $dp[2]$ 都无法达到，初始化为 $-1$。

5. 最终结果

$dp[0]$ 就是模 $3$ 余 $0$ 的最大和，即能被 $3$ 整除的最大和。

结合示例 1 走一遍：

$nums = [3,6,5,1,8]$

初始化：$dp = [0, -1, -1]$

• $num = 3, r = 0$：$dp[0]+3=3$，新余数 $0$ → $dp=[3,-1,-1]$
• $num = 6, r = 0$：$dp[0]+6=9$，新余数 $0$ → $dp=[9,-1,-1]$
• $num = 5, r = 2$：$dp[0]+5=5$，新余数 $2$ → $dp=[9,-1,5]$
• $num = 1, r = 1$：
  • $dp[0]+1=1$，新余数 $1$ → $dp=[9,1,5]$
  • $dp[2]+1=6$，新余数 $0$ → $dp=[9,1,5] \to \max(9,6)=9$ → $dp=[9,1,5]$
• $num = 8, r = 2$：
  • $dp[0]+8=8$，新余数 $2$ → $dp=[9,1,\max(5,8)=8]$
  • $dp[1]+8=9$，新余数 $0$ → $dp=[\max(9,9)=9,1,8]$
  • $dp[2]+8=13$，新余数 $1$ → $dp=[9,\max(1,13)=13,8]$

结果 $dp[0] = 9$... 但这和示例答案 $18$ 不一致。让我重新检查。

啊，我明白了。上面的过程中，我处理每个数字的方式不对。当 $num=3$ 时，$dp[0]+3=3$，但原来 $dp[0]=0$，所以我们需要保留「不选」的情况。

正确的做法是在更新时使用备份数组，或者同时考虑选与不选。

让我重新来处理：

初始化：$dp = [0, -1, -1]$

对于 $num = 3, r = 0$：

• $dp = [0, -1, -1]$，复制为 $new\_dp = [0, -1, -1]$
• $i=0$：$new\_dp[0] = \max(0, 0+3) = 3$
• $i=1$：跳过（$-1$）
• $i=2$：跳过（$-1$）
• $dp = [3, -1, -1]$

对于 $num = 6, r = 0$：

• $dp = [3, -1, -1]$，复制为 $new\_dp = [3, -1, -1]$
• $i=0$：$new\_dp[0] = \max(3, 3+6) = 9$
• $dp = [9, -1, -1]$

对于 $num = 5, r = 2$：

• $dp = [9, -1, -1]$，复制为 $new\_dp = [9, -1, -1]$
• $i=0$：$new\_dp[2] = \max(-1, 9+5) = 14$
• $dp = [9, -1, 14]$

对于 $num = 1, r = 1$：

• $dp = [9, -1, 14]$，复制为 $new\_dp = [9, -1, 14]$
• $i=0$：$new\_dp[1] = \max(-1, 9+1) = 10$
• $i=2$：$new\_dp[0] = \max(9, 14+1) = 15$
• $dp = [15, 10, 14]$

对于 $num = 8, r = 2$：

• $dp = [15, 10, 14]$，复制为 $new\_dp = [15, 10, 14]$
• $i=0$：$new\_dp[2] = \max(14, 15+8) = 23$
• $i=1$：$new\_dp[0] = \max(15, 10+8) = 18$
• $i=2$：$new\_dp[1] = \max(10, 14+8) = 22$
• $dp = [18, 22, 23]$

结果 $dp[0] = 18$ ✓

好的，这个示例的计算过程可以不用在文件中写太细，但需要保证解释清晰。

思路 1：代码

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        # dp[r] 表示当前能得到的模 3 余 r 的最大和
        # -1 表示该状态暂时不可达
        dp = [-1, -1, -1]
        dp[0] = 0

        for num in nums:
            r = num % 3
            # 复制当前状态，用于同时处理所有转移
            new_dp = dp[:]
            for i in range(3):
                if dp[i] != -1:
                    # 将 num 加入余数为 i 的状态
                    new_r = (i + r) % 3
                    new_dp[new_r] = max(new_dp[new_r], dp[i] + num)
            dp = new_dp

        return dp[0]

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $nums$ 的长度。每个数字只需要 $O(1)$ 时间处理（$3$ 个状态的更新）。
• 空间复杂度：$O(1)$，只使用了一个长度为 $3$ 的数组。