题目

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

解答 & 代码

动态规划：

动态规划数组 **dp**：
- dp[i][0] 代表只从前 i 个元素中选取，和除 3 余 0 的最大和
- dp[i][1] 代表只从前 i 个元素中选取，和除 3 余 1 的最大和
- dp[i][2] 代表只从前 i 个元素中选取，和除 3 余 2 的最大和
状态转移方程：
- dp[i][0] = max(dp[i - 1][0], dp[i - 1][((0 - val) % 3 + 3) % 3] + val)
  - dp[i - 1][0] 代表不取第 i - 1 个元素时，和除 3 余 0 的最大和
  - dp[i - 1][**((0 - val) % 3 + 3) % 3**] + val 代表取第 i - 1 个元素时，和除 3 余 0 的最大和。val = nums[i - 1]
- dp[i][1] = max(dp[i - 1][1], dp[i - 1][((1 - val) % 3 + 3) % 3] + val)
- dp[i][2] = max(dp[i - 1][2], dp[i - 1][((2 - val) % 3 + 3) % 3] + val)

初始化：

dp[0][0] = 0：只能取前 0 个元素（即没有数字可以取），则和只能为 0，除 3 余 0
dp[0][1] = INT_MIN：只能取前 0 个元素（即没有数字可以取），则和只能为 0，除 3 余 0，不可能余 1，因此设为 INT_MIN，避免后续取 max 被选择

dp[0][2] = INT_MIN：只能取前 0 个元素（即没有数字可以取），则和只能为 0，除 3 余 0，不可能余 2，因此设为 INT_MIN，避免后续取 max 被选择

class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
   int len = nums.size();
   vector<vector<int>> dp(len + 1, vector<int>(3, INT_MIN));
   dp[0][0] = 0;
   for(int i = 1; i <= len; ++i)
   {
       int val = nums[i - 1];
       dp[i][0] = max(dp[i - 1][0], dp[i - 1][((0 - val) % 3 + 3) % 3] + val);
       dp[i][1] = max(dp[i - 1][1], dp[i - 1][((1 - val) % 3 + 3) % 3] + val);
       dp[i][2] = max(dp[i - 1][2], dp[i - 1][((2 - val) % 3 + 3) % 3] + val);
   } 
   return  dp[len][0] < 0 ? 0 : dp[len][0];
}
};

复杂度分析：设数组长度为 N

时间复杂度 O(N)：
空间复杂度 O(N)：二维 dp 的空间占用为 3N

执行结果：

执行结果：通过

执行用时：68 ms, 在所有 C++ 提交中击败了 28.08% 的用户
内存消耗：37.4 MB, 在所有 C++ 提交中击败了 16.97% 的用户

类似题目

美团算法暑期实习笔试 2022.03.26

hot 100

[中等] 1262. 可被三整除的最大和

题目

解答 & 代码

类似题目