第 172 场双周赛——3780. 能被 3 整除的三元组最大和

题目链接：3780. 能被 3 整除的三元组最大和（中等）

算法原理：

解法：分类讨论 + 贪心 + 枚举

154ms击败46.80%

时间复杂度O(Nlogn)

①分组：将数组元素按 “模 3 的结果” 分为 3 组（余 0→mod0、余 1→mod1、余 2→mod2）
②排序：每组内降序排序，方便快速取组内最大元素
计算有效组合的和：
③情况 1：同组取 3 个（同余 3 数的和必是 3 的倍数），若组内元素≥3，取前 3 大元素相加
④情况 2：三组各取 1 个（0+1+2 的和必是 3 的倍数），若三组均至少有 1 个元素，取每组最大元素相加
⑤取最大值：从所有有效组合的和中取最大值；若数组长度不足 3，直接返回 0

Java代码：

class Solution { public int maximumSum(int[] nums) { int n=nums.length,ret=0; if(n<3) return 0; List<Integer> mod0=new ArrayList<>(); List<Integer> mod1=new ArrayList<>(); List<Integer> mod2=new ArrayList<>(); for(int x:nums){ if(x%3==0) mod0.add(x); else if(x%3==1) mod1.add(x); else mod2.add(x); } //对每个集合降序，方便取最大值 Collections.sort(mod0,(a,b)->b-a); Collections.sort(mod1,(a,b)->b-a); Collections.sort(mod2,(a,b)->b-a); int size0=mod0.size(),size1=mod1.size(),size2=mod2.size(); if(size0>=3) ret=Math.max(ret,mod0.get(0)+mod0.get(1)+mod0.get(2)); if(size1>=3) ret=Math.max(ret,mod1.get(0)+mod1.get(1)+mod1.get(2)); if(size2>=3) ret=Math.max(ret,mod2.get(0)+mod2.get(1)+mod2.get(2)); if(size0>=1&&size1>=1&&size2>=1) ret=Math.max(ret,mod0.get(0)+mod1.get(0)+mod2.get(0)); return ret; } }