主题切换
LeetCode 每日一题笔记
0. 前言
- 日期：2025.11.23
- 题目：1262.可被三整除的最大和
- 难度：中等
- 标签：数组 贪心 动态规划
1. 题目理解
问题描述：
给你一个整数数组 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 整除的最大和）。
2. 解题思路
核心观察
算法步骤
3. 代码实现
java
class lc3600_lc3699.lc3660.Solution {
public int maxSumDivThree(int[] nums) {
Arrays.sort(nums);
int max=0;
int m1[]=new int[nums.length];
int m2[]=new int[nums.length];
for(int i=0;i<m1.length;i++){
m1[i]=m2[i]=Integer.MAX_VALUE;
}
int pos1=0;
int pos2=0;
for(int i: nums){
max+=i;
if(i%3==1){
m1[pos1]=i;
pos1++;
}
if(i%3==2){
m2[pos2]=i;
pos2++;
}
}
if(max%3==2){
if(pos1>1&&m1[0]+m1[1]<m2[0]){
return max-m1[0]-m1[1];
}
System.out.println("f");
return max-m2[0];
}
else if(max%3==1){
if(pos2>1&&m2[0]+m2[1]<m1[0]){
return max-m2[0]-m2[1];
}
return max-m1[0];
}
else return max;
}
}