题目大意：
可被三整除的最大和
给你一个整数数组 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1262
解题思路分析：
这道题可以使用动态规划来解题，但是DP数组不太好设置，理解起来有些困难，因此采取了另外一种方式。我们可以将数组中的数字分成3类，
- 除以3余1的数
- 除以3余2的数
- 能被3整除的数
不论最优解是什么，结果中一定包含所有能被3整除的数字。因此我们应该在余数为1和2的数字中找到和能被3整除的最大和。这道题的解法用到一个简单的数学知识，即：
- 如果一个数除以3余1的话，那么它再减去一个除以3余1的数，差值可被3整除，或者减去2个除以3余2的数字，同样差值可以被3整除。
- 如果一个数除以3余2的话，那么它再减去一个除以3余2的数，差值可被3整除，或者减去2个除以3余1的数字，同样差值可以被3整除。
因此，解题思路也就清晰了，我们先计算出数组中所有数字之和，如何和能被3整除，可直接作为结果返回。如果总和除以3余1的话，我们可以减去一个最小的余数为1的数，或者减去2个最小的余数为2的数，求两者最大值作为最优解返回。如果总和除以3余2的话，同理，我们可以减去一个最小的余数为2的数，或者减去2个最小的余数为1的数，返回一个最优解。
实现代码：
public int maxSumDivThree(int[] nums) {
int minRemain1=Integer.MAX_VALUE; // 除以3余1的最小数
int secMinRemain1=Integer.MAX_VALUE; // 除以3余1的次小数
int minRemain2=Integer.MAX_VALUE; // 除以3余2的最小数
int secMinRemain2=Integer.MAX_VALUE; // 除以3余2的次小数
int sum=0; // 总和
for(int num : nums){ // 循环每一个数字
sum+=num; // 计算和
if(num%3==1){ // 如果当前数除以3余1
// 更新余1的数字的最小数和次小数
if(num<=minRemain1){
secMinRemain1=minRemain1;
minRemain1=num;
}else if(num<=secMinRemain1){
secMinRemain1=num;
}
}else if(num%3==2){ // 如果当前数除以3余2
// 更新余2的数字的最小数和次小数
if(num<=minRemain2){
secMinRemain2=minRemain2;
minRemain2=num;
}else if(num<=secMinRemain2){
secMinRemain2=num;
}
}
}
// 如果总和除以3余0，直接返回总和
if(sum%3==0){
return sum;
}else if(sum%3==1){ // 如果总和除以3余1
// 如果数组中不存在2个余2的数字
if(minRemain2==Integer.MAX_VALUE
|| secMinRemain2==Integer.MAX_VALUE){
return sum-minRemain1; // 返回总和减去一个最小的余1的数
}else{
// 看余1的最小数，2个最小余2的数之和哪个更小，
// 用总和减去小的一方作为结果返回
return sum-Math.min(minRemain1,minRemain2+secMinRemain2);
}
}else{ // 如果总和除以3余2
// 如果数组中不存在2个余1的数字
if(minRemain1==Integer.MAX_VALUE
|| secMinRemain1==Integer.MAX_VALUE){
return sum-minRemain2; // 返回总和减去一个最小的余2的数
}else{
// 看余2的最小数，2个最小余1的数之和哪个更小，
// 用总和减去小的一方作为结果返回
return sum-Math.min(minRemain2,minRemain1+secMinRemain1);
}
}
} 本题解法执行时间为4ms。
Runtime: 4 ms, faster than 98.03% of Java online submissions for Greatest Sum Divisible by Three.
Memory Usage: 43.5 MB, less than 100.00% of Java online submissions for Greatest Sum Divisible by Three.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1262-greatest-sum-divisible-by-three-解题思路分析/