发表于 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 题目链接