1. 问题描述：
给你一个整数数组 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^41 <= nums[i] <= 10^4来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three
2. 思路分析：
① 根据题目可以知道存在状态转移的特点，通过之前的余数的情况来得到当前的余数的情况，所以应该使用动态规划的策略来解决，而动态规划的难点就在于如何想到合适的策略来解决问题，可以知道题目中相加之和的结果存在余数为0,1,2三种情况，而我们要求解的是能够被3整除的最大和所以需要根据之前余数为0,1,2的dp列表来的得到当前下标对应的dp列表的值
② 记录余数为1,2是为了得到上一次最大的余数为1,2的最大整数和，如果加上当前的整数得到可能的余数为0说明整数和就更大了，得到的能够被3整除的和就更大了，所以需要记录余数为0,1,2的情况，在循环的时候根据当前的数字除以3的余数情况来更新dp列表的值
3. 代码如下：
class Solution: def maxSumDivThree(self, nums: List[int]) -> int: # 在初始化的时候注意一个参数是列第二个参数是行 # 初始化二维列表 dp = [[0] * 3 for i in range((len(nums) + 1))] # print(dp) dp[0][0], dp[0][1], dp[0][2] = 0, -sys.maxsize, -sys.maxsize for i in range(1, len(nums) + 1): if nums[i - 1] % 3 == 0: dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]) dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]) elif nums[i - 1] % 3 == 1: dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]) dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]) elif nums[i - 1] % 3 == 2: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]) dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]) return dp[len(nums)][0]
