详细介绍：LeetCode 每日一题笔记日期：2025.11.23 题目：1262.可被三整除的最大和-尧图网站建设

📅 发布时间：2026/6/22 2:27:13

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 整除的最大和）。

关键分析：

目标是找到子数组（或子集）和的最大值，且该和能被 3 整除；
若数组所有元素和本身能被 3 整除，直接返回该和；
若和不能被 3 整除，需通过移除最小的“代价”（即最小的元素或元素组合），使剩余和能被 3 整除，且保证剩余和最大。

2. 解题思路

核心观察

数组所有元素的总和 max 是“潜在最大和”，若 max % 3 == 0，直接返回 max；
若 max % 3 == 1：需移除以下两种情况中“代价最小”的一种（保证剩余和最大）：
- 移除 1 个“模 3 余 1”的最小元素；
- 移除 2 个“模 3 余 2”的最小元素（缘于 2+2=4 ≡1 mod3，移除后总和模3为0）；
若 max % 3 == 2：需移除以下两种情况中“代价最小”的一种：
- 移除 1 个“模 3 余 2”的最小元素；
- 移除 2 个“模 3 余 1”的最小元素（因为 1+1=2 ≡2 mod3，移除后总和模3为0）；
提前对数组排序，确保收集到的“模 3 余 1”和“模 3 余 2”的元素是从小到大排列的，方便取最小代价。

算法步骤

对数组排序（从小到大），便于后续获取“模 3 余 1”和“模 3 余 2”的最小元素；
初始化两个数组 m1 和 m2，分别存储“模 3 余 1”和“模 3 余 2”的元素，初始值设为 Integer.MAX_VALUE（表示未填充）；
遍历数组，计算所有元素的总和 max，同时将“模 3 余 1”的元素存入 m1，“模 3 余 2”的元素存入 m2；
根据 max % 3 的结果，计算需要移除的最小代价，得到最终能被 3 整除的最大和；
特殊情况：若移除后无元素剩余（如数组只有一个元素且不能被 3 整除），返回 0。

3. 代码实现

import java.util.Arrays;
class Solution {
public int maxSumDivThree(int[] nums) {
Arrays.sort(nums); // 对数组排序，方便后续获取最小的余1、余2元素
int max = 0; // 存储数组所有元素的总和（潜在最大和）
int m1[] = new int[nums.length]; // 存储模3余1的元素，初始为最大值（未填充状态）
int m2[] = new int[nums.length]; // 存储模3余2的元素，初始为最大值（未填充状态）
// 初始化m1和m2数组，所有元素设为Integer.MAX_VALUE（表示未使用的位置）
for(int i = 0; i < m1.length; i++){
m1[i] = m2[i] = Integer.MAX_VALUE;
}
int pos1 = 0; // m1数组的填充指针（记录当前存储到第几个余1元素）
int pos2 = 0; // m2数组的填充指针（记录当前存储到第几个余2元素）
// 遍历数组，计算总和并分类存储余1、余2的元素
for(int i : nums){
max += i; // 累加总和
if(i % 3 == 1){
m1[pos1] = i; // 存入余1元素
pos1++; // 指针后移
}
if(i % 3 == 2){
m2[pos2] = i; // 存入余2元素
pos2++; // 指针后移
}
}
// 情况1：总和模3余2，需移除最小代价使总和模3为0
if(max % 3 == 2){
// 可选方案：移除2个最小的余1元素（若存在），且代价小于移除1个最小的余2元素
if(pos1 > 1 && m1[0] + m1[1] < m2[0]){
return max - m1[0] - m1[1]; // 移除两个余1最小元素
}
// 否则：移除1个最小的余2元素（需确保存在余2元素）
return (pos2 > 0) ? max - m2[0] : 0;
}
// 情况2：总和模3余1，需移除最小代价使总和模3为0
else if(max % 3 == 1){
// 可选方案：移除2个最小的余2元素（若存在），且代价小于移除1个最小的余1元素
if(pos2 > 1 && m2[0] + m2[1] < m1[0]){
return max - m2[0] - m2[1]; // 移除两个余2最小元素
}
// 否则：移除1个最小的余1元素（需确保存在余1元素）
return (pos1 > 0) ? max - m1[0] : 0;
}
// 情况3：总和本身能被3整除，直接返回总和
else return max;
}
}