leetcode [1262] 可被三整除的最大和

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给你一个整数数组 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^4
1 <= nums[i] <= 10^4

来自题解:

我们用 f[i][j] 表示前 i 个数中选取了若干个数，并且它们的和模 3 余 j 时，这些数的和的最大值。那么对于当前的数 nums[i]，如果我们选取它，那么就可以通过 f[i - 1][j0] 转移得来，其中 (j0 + nums[i]) % 3 == j % 3；如果我们不选取它，就可以通过 f[i - 1][j] 转移得来。因此我们可以写出如下的状态转移方程：

f[i][j] = max(f[i - 1][j], f[i - 1][(j - nums[i]) % 3] + nums[i])
f[0][0] = 0
f[0][i] = N/A

由于 (j - nums[i]) % 3 可能会引入负数，因此这道题用递推的形式来实现动态规划较为方便：

f[i - 1][j] -> f[i][j]
f[i - 1][j] + nums[i] -> f[i][(j + nums[i]) % 3]
f[0][0] = 0
f[0][i] = N/A

我们还可以发现，所有的 f[i][..] 只会从 f[i - 1][..] 转移得来，因此我们在动态规划时只存储这两行的结果，减少空间复杂度。

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        f = [0, -1, -1]
        for num in nums:
            g = f[:]
            for i in range(3):
                if f[i] != -1:
                    g[(i + num % 3) % 3] = max(g[(i + num % 3) % 3], f[i] + num)
            f = g
        return f[0]