可被三整除的最大和

可被三整除的最大和

给你一个整数数组 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余数相同）
那这样就可以分三种情况：

1. 总和余数为0，那么就意味着所有数相加就能满足条件，所以我们就不需要再减去任何数了。
2. 总和余数为1，那么就意味着我们需要减去一部分(这部分除以3余数也是1)，并且要求这部分最小化，那么我们可以明显的感觉到排完序之后更好找一些，就是从小到大取。减去这部分要求余数为1，又有两种情况
   1. 只减去一个余数为1的数
   2. 减去两个余数为2的数
3. 总和余数为2，与总和余数为1的相似，只不过两种情况为：
   1. 只减去一个余数为2的数
   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;
    }
};