可被三整除的最大和
给你一个整数数组 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 整除的最大和）。
解题思路：
因为要求最大，所以我们这样可以将问题转换成总和减去最小的（除以3余数和总和除以3余数相同）
那这样就可以分三种情况：
- 总和余数为0，那么就意味着所有数相加就能满足条件，所以我们就不需要再减去任何数了。
- 总和余数为1，那么就意味着我们需要减去一部分(这部分除以3余数也是1)，并且要求这部分最小化，那么我们可以明显的感觉到排完序之后更好找一些，就是从小到大取。减去这部分要求余数为1，又有两种情况
- 只减去一个余数为1的数
- 减去两个余数为2的数
- 总和余数为2，与总和余数为1的相似，只不过两种情况为：
- 只减去一个余数为2的数
- 减去两个余数为3的数
所以余数是0(整除3)的数不用管，因为它只会影响结果的大小，不会影响结果的余数。
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
}
int ans=sum%3;
//cout<<ans<<" "<<sum<<endl;
if(ans==0) return sum;
else if(ans==1){
// 有一个余数为1
int one=0,two=0;
int flag=0;
for(int i=0;i<n;i++){
if(nums[i]%3==1&&one==0){
one=nums[i];
}
else if(nums[i]%3==2){
if(flag==0){
two=nums[i];
flag=1;
}else if(flag==1){
two+=nums[i];
flag=2;
}
}
}
if(one!=0){
if(flag==2){
return sum-min(one,two);
}else return sum-one;
}else if(flag==2){
return sum-two;
}
}else if(ans==2){
int one=0,two=0;
int flag=0;
for(int i=0;i<n;i++){
if(nums[i]%3==2&&two==0){
two=nums[i];
}
else if(nums[i]%3==1){
if(flag==0){
one=nums[i];
flag=1;
}else if(flag==1){
one+=nums[i];
flag=2;
}
}
}
if(two!=0){
if(flag==2){
return sum-min(one,two);
}else return sum-two;
}else if(flag==2){
return sum-one;
}
}
return 0;
}
};
