1262. 可被三整除的最大和
难度中等81
给你一个整数数组 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 class Solution { public: int maxSumDivThree(vector<int>& nums) { vector<int> dp(3); dp[0]=0,dp[1]=0x80000000,dp[2]=0x80000000; for(int i=0;i<nums.size();++i) { int mode=nums[i]%3; int old_fit_dp[3]; for(int j=0;j<3;++j) old_fit_dp[j]=dp[(3+j-mode)%3]; for(int j=0;j<3;++j) dp[j]=max(dp[j],old_fit_dp[j]+nums[i]); } return dp[0]; } };
};
