1262. 可被三整除的最大和（leetcode）

题目描述

给你一个整数数组 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<=arr.length<=10^5$
$-10^4<=arr[i]<=10^4$

题解1（C++版本）

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > dp(n + 1, vector<int>(3, 0)); // dp[i][j]表示选择前i个元素中若干个数的和，模3之后的余数为j
        for(int i = 1; i <= n; i++){
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][1];
            dp[i][2] = dp[i - 1][2];
            for(int j = 0; j < 3; j++){
                int sum = dp[i - 1][j] + nums[i - 1];
                int t = sum % 3;
                dp[i][t] = max(sum, dp[i][t]);
            }
        }
        return dp[n][0];
    }
};