目录
力扣1262. 可被三整除的最大和
解析代码
力扣1262. 可被三整除的最大和
1262. 可被三整除的最大和
难度 中等
给你一个整数数组 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) {
}
};解析代码
正难则反： 可以先把所有的数累加在一起，然后根据累加和的结果，贪心地删除一些数。
分类讨论：设累加和为 sum ，用 x 标记 %3 == 1 的数，用 y 标记 % 3 == 2 的数。那么根据 sum 的余数，可以分为下面三种情况：（求最小的值和次小的值可以直接sort，也可以在求数组和的时候记录下来，时间就变为了O（N））。
- sum % 3 == 0 ，此时所有元素的和就是满足要求的，直接返回。
- sum % 3 == 1，此时数组中要么存在一个x（x % 3 == 1），要么存在两个y（y % 3 == 2）。因为我们要的是最大值，所以应该选择 x 中最小的那么数，记为 x1 ，或者是 y 中最小以及次小的两个数，记为 y1, y2 。那么，我们应该选择两种情况下的最大值： max(sum - x1, sum - y1 - y2)
- sum % 3 == 2，此时数组中要么存在一个 y（y % 3 == 2），要么存在两个 x（x % 3 == 1） 。因为我们要的是最大值，所以应该选择 y 中最小的那个数，记为 y1 ，或者是 x 中最小以及次小的两个数，记为 x1, x2 。
那么应该选择下面两种情况下的最大值： max(sum - y1, sum - x1 - x2) ；
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
const int INF = 0x3f3f3f3f;
int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;
for(auto& x : nums)
{
sum += x;
if(x % 3 == 1) // 找出x % 3 == 1中x最小的和次小的
{
if(x < x1)
x2 = x1, x1 = x;
else if(x < x2)
x2 = x;
}
else if(x % 3 == 2) // 找出x % 3 == 2中x最小的和次小的
{
if(x < y1)
y2 = y1, y1 = x;
else if(x < y2)
y2 = x;
}
}
if(sum % 3 == 1)
sum = max(sum - x1, sum - y1 - y2);
else if(sum % 3 == 2)
sum = max(sum - y1, sum - x1 - x2);
return sum;
}
};
