-
发表于 2024.07.15
-
比较容易想到使用动态规划的方法,定义
dp[j][i]
(其中0 <= i < 3
)表示数组前j
个元素中,模3
余数为i
的最大和。遍历数组,对于每一个nums[j]
,更新dp[j][(i + nums[j]) % 3] = max(dp[j - 1][(i + nums[j]) % 3], dp[j - 1][i] + nums[j])
。最终的答案就是dp[len(nums) - 1][0]
。需要注意的是,由于dp
元素的初始值为0
,如果在更新数组的过程中,发现上一个状态dp[j - 1][i]
为0
,且i != nums[j] % 3
,则直接跳过,因为为0
意味着前面数组中完全找不到模3
余数为i
的和。如果dp[j - 1][i]
为0
,且i == nums[j] % 3
,则直接更新dp[j][i] = nums[j]
,意味着当前元素就是模3为i
最大和。class Solution: def maxSumDivThree(self, nums: List[int]) -> int: mod_to_max_sum = [0] * 3 for num in nums: new_arr = list(mod_to_max_sum) m = num % 3 if mod_to_max_sum[m] == 0: new_arr[m] = num for i in range(3): if mod_to_max_sum[i] != 0: new_arr[(i + m) % 3] = max(mod_to_max_sum[(i + m) % 3], mod_to_max_sum[i] + num) mod_to_max_sum = new_arr return mod_to_max_sum[0]
官解的dp解法,将模
3
为1
和2
的初始值定义为inf
,这样在更新dp[j][i]
时,如果dp[j - 1][i]
为inf
,相加后还是inf
,这样就可以避免了上面的判断。class Solution: def maxSumDivThree(self, nums: List[int]) -> int: f = [0, -float("inf"), -float("inf")] for num in nums: g = f[:] for i in range(3): g[(i + num % 3) % 3] = max(g[(i + num % 3) % 3], f[i] + num) f = g return f[0]
- LC 题目链接
-