【Leetcode Daily】1262可被三整除的最大和

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整数数组，可任意选取其中数字求和，找到其中和能被 3 整除的最大值。

思路分享

• 对于动态规划而言，可以采用选或不选的思路。对前 n 个数字而言，选取第 n 个数字时，如果此时和能被 3 除后的余数为 0（也就是正好整除），那么就可以转为选取第 n-1 个数字时，需要和能被 3 除后，余数为 (0+nums[n]) %3。

  https://leetcode.cn/problems/greatest-sum-divisible-by-three/solutions/2313700/liang-chong-suan-fa-tan-xin-dong-tai-gui-tsll/?envType=daily-question&envId=2025-11-23

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        # 空间优化
        n = len(nums)
        f = [[-inf]*3 for _ in range(2)]
        f[0][0] = 0
        for i in range(n):
            for j in range(3):
                f[(i+1)%2][j] = max(f[i%2][j], f[i%2][(j+nums[i])%3]+nums[i])
        return f[n%2][0]
        # 递推
        # f[i][j] = max(f[i-1][j], (f[i-1][j+nums[i]]%3) + nums[i])
        n = len(nums)
        f = [[-inf]*3 for _ in range(n+1)]
        f[0][0] = 0
        for i in range(n):
            for j in range(3):
                f[i+1][j] = max(f[i][j], f[i][(j+nums[i])%3]+nums[i])
        return f[-1][0]
        # 记忆化搜索 前 i 元素中，模 3 为 j 的最大和
        @cache
        def dfs(i:int, j:int)->int:
            if i < 0:
                return -inf if j!=0 else 0
            return max(dfs(i-1, j), dfs(i-1, (j+nums[i])%3)+nums[i])
        return dfs(len(nums)-1, 0)