地址 https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/
题目描述
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
示例 ： 输入：nums = [,,,,]
输出：
解释：选出数字 , , 和 ，它们的和是 （可被 整除的最大和）。
示例 ： 输入：nums = []
输出：
解释： 不能被 整除，所以无法选出数字，返回 。
示例 ： 输入：nums = [,,,,]
输出：
解释：选出数字 , , 以及 ，它们的和是 （可被 整除的最大和）。
提示： <= nums.length <= * ^
<= nums[i] <= ^
算法1
最后数组和 只有三种情况
1 除以3余0 直接返回
2 除以3余1 那么要么减少一个除以3余1的数字 或者减少两个除以3余2的数字
3 除以3余2 那么要么减少一个除以3余2的数字 要么减少两个除以3余1的数字
class Solution {
public:
vector<int> v[];
int Check(int singleIdx,int doubleIdx,int sum)
{
if (v[doubleIdx].size() < ) {
return sum - v[singleIdx][];
}
else if (v[singleIdx].size() == ) {
return sum - v[doubleIdx][] - v[doubleIdx][];
}
else {
int rem = v[singleIdx][];
if (rem > (v[doubleIdx][] + v[doubleIdx][])) rem = (v[doubleIdx][] + v[doubleIdx][]);
return sum - rem;
}
}
int maxSumDivThree(vector<int>& nums) {
int sum = ;
for (int i = ; i < nums.size(); i++)
{
sum += nums[i];
if (nums[i] % == ) {
v[].push_back(nums[i]);
}
else if(nums[i] % == ){
v[].push_back(nums[i]);
}
}
sort(v[].begin(), v[].end());
sort(v[].begin(), v[].end());
int sum_n = sum % ;
if (sum_n == ) return sum;
if (sum_n == ) {
//减少两个v2 和一个v1 选择
return Check( , ,sum);
}
if(sum_n == ){
return Check( , ,sum);
}
return -;
}
};