JZX轻语：简
LeetCode 1262 - 可被三整除的最大和
发表于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]