文章目录
Greatest Sum Divisible by Three 可被三整除的最大和
问题描述：
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
nums.length 范围[1,40000] , n u m s [ i ] nums[i] nums[i] 范围[1,10000]
分析
要从这个数组中找到一些数而且他们的和可以被3整除，还需要最大。
第一个思路就是BF，穷举所有的可能组合，然后check，从而找到结果。思路没问题，但是以穷举组合的方式，时间复杂度必然是指数级的。所以穷举的思路可以洗洗睡了。
观察要求，如果要满足和被3整除，那么可以把原数组的元素进行分类，每个元素对3求余，余数为0,1,2。余数为0的元素肯定是要全部累加的。剩余的就是1,2。
能想到这里的基本就完成一半了，为了达到最大，一定是从余数1和2中，挑最大的匹配，这样就可以得到更大的和。
求余就是为了拼凑被3整除，但是问题在于，此时余数1,2的元素，要怎么选。
记余数为1和2的数组分别为A,B，要做的就是从A中找X个，B中找Y个， s u m X + s u m Y sumX+sumY sumX+sumY最大。
这种方案是不一定的，可能是从A中找出 X = 3 k X=3k X=3k个元素满足被3整除最大，也可能是仅从B中找出 Y = 6 k Y=6k Y=6k个元素被3整除最大，或者是A中出 k k k个，B中出 k k k个。 k > = 1 k>=1 k>=1.
当然也有可能不存在这样的方案。也就是当一个为空，或者是单独的一个数组不够构成被3整除的组合。
既然正向不容易，那就反过来思考。
把所有元素加和 s u m sum sum， s u m m o d 3 = k sum\mod 3=k summod3=k,如果 k = = 0 k==0 k==0,sum自己就是结果。如果 k = = 1 k==1 k==1,说明sum要减掉一个余数为1的最小数，或者是去掉2个余数为2的最小数。
如果 k = = 2 k==2 k==2,说明sum要减掉一个余数为2的最小数，或者是去掉2个余数为1的最小数。
这种做减法的策略，可以保证覆盖到所有的情况。
代码
class Solution {public int maxSumDivThree(int[] nums) {int sum = 0;for (int x : nums) {sum += x;}if (sum % 3 == 0) return sum;List<Integer> a1 = new ArrayList<Integer>();List<Integer> a2 = new ArrayList<Integer>();for (int x : nums) {if (x % 3 == 1) a1.add(x);else if (x % 3 == 2) a2.add(x);}Collections.sort(a1);Collections.sort(a2);if (sum % 3 == 2) { // swap(a1,a2)List<Integer> tmp = a1;a1 = a2;a2 = tmp;}int ans = a1.isEmpty() ? 0 : sum - a1.get(0);if (a2.size() > 1)ans = Math.max(ans, sum - a2.get(0) - a2.get(1));return ans;}
}
时间复杂度O(NlogN)
空间复杂度O(N)
代码来源于灵神大佬，非常简洁，值得学习。
Tag
Greedy Array Dynamic Programming
本文链接：https://my.lmcjl.com/post/4352.html
4 评论