<jupyter_start><jupyter_text>说明：    给你一个整数数组 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、1 <= nums.length <= 4 * 10^4    2、1 <= nums[i] <= 10^4<jupyter_code>class Solution:
    def maxSumDivThree(self, nums) -> int:
        N = len(nums)
        dp = [[0] * 3 for _ in range(N)] # 列数：0, 1, 2 表示余数是多少
        dp[0][nums[0] % 3] = nums[0]
        
        for i in range(1, N):
            for j in range(3):
                dp[i][j] = dp[i-1][j] # 在原来的基础上，准备加下一个数
            
            for j in range(3):
                cur_val = dp[i-1][j] + nums[i]
                idx = cur_val % 3 # 加下一个数后余数的值
                dp[i][idx] = max(dp[i][idx], cur_val)
        return dp[-1][0]
solution = Solution()
solution.maxSumDivThree([3,6,5,1,8])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1707070707070707, 'fraction_numerical': 0.0696969696969697, 'mean_word_length': 2.1261829652996846, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '377808', 'license': 'Apache-2.0', 'n_tokens_mistral': 553, 'n_tokens_neox': 536, 'n_words': 96, 'path': 'Dynamic Programming/1030/1262. Greatest Sum Divisible by Three.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '990'}