LeetCode 1262. 可被三整除的最大和

约 5 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 腾讯 字节 微软 美团 小米
标签
数组 动态规划 排序 贪心

题目描述

✅ 1262. 可被三整除的最大和

image-20260928214546447

题意分析

从正整数数组中任意选择一些元素，使它们的和能被 3 整除，并且这个和尽可能大。每个位置最多选一次，不要求所选元素在数组中连续。

可以一个元素也不选，空集的和为 0，因此答案始终存在。判断能否被三整除只需要余数，而最大化目标又要求保留具体的和，可以把所有候选子集按余数 0、1、2 分成三类维护。

解法：按余数维护最大和动态规划

核心思路

[!blue]

令 dp[r] 表示只使用已经处理过的元素，能够得到的余数为 r 的最大和。对余数相同的两个和，只保留较大者就足够：以后再选择相同的一组元素，两者的余数变化完全一样，较大的和仍然更大，所以较小者不可能产生更优答案。

初始还没有处理任何元素，只有空集可选，因此 dp[0] = 0，另外两个余数不可达，用 -1 标记。输入都是正数，真实可达和不会为负，能够与这个标记明确区分；不可达状态不能参与加法转移。

处理当前值 num 时，先复制 dp 得到 next，保留不选它的全部结果。然后枚举每个可达旧状态 dp[r]，计算选择后的 sum = dp[r] + num，用它更新 next[sum % 3] 的最大值。这样选与不选两种可能都被覆盖，同余状态继续只保留最大和。

所有选择转移必须读取同一份旧 dp。如果直接读写一个数组，本轮刚加入 num 的新状态可能再次加上 num，就把一个位置重复使用了。Java 的 clone() 和 Go 的固定数组赋值都创建本轮快照，写 next 不会影响正在读取的旧状态。

一轮结束后再令 dp = next，使状态对应多处理了一个元素的前缀。每个位置只贡献一次选或不选，且每类状态都保留最优和；遍历结束后只返回余数为零的 dp[0]，不能返回另外两类中更大但不能整除的值。

解题步骤

  1. 初始化三个余数状态为 0、-1、-1。
  2. 对每个 num，复制旧状态得到 next，表示先保留不选择它的方案。
  3. 枚举 r = 0, 1, 2，跳过负值标记的不可达状态。
  4. 计算 sum = dp[r] + num，用较大值更新 next[sum % 3]。
  5. 全部旧状态转移完后令 dp = next，继续处理下一个元素。
  6. 返回最终的 dp[0]。

代码实现

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = {
            0,
            -1,
            -1
        };

        for (int num : nums) {
            // 先保留不选当前元素的状态，所有选择转移只读取旧数组。
            int[] next = dp.clone();

            for (int r = 0; r < 3; r++) {
                // 不可达余数没有真实子集，不能参与加法转移。
                if (dp[r] < 0) {
                    continue;
                }

                int sum = dp[r] + num;
                int remainder = sum % 3;

                next[remainder] = Math.max(next[remainder], sum);
            }

            dp = next;
        }

        return dp[0];
    }
}

func maxSumDivThree(nums []int) int {
    dp := [3]int{
        0,
        -1,
        -1,
    }

    for _, num := range nums {
        // 固定数组按值复制，所有选择转移只读取旧状态。
        next := dp
        for r := 0; r < 3; r++ {
            // 不可达余数没有真实子集，不能参与加法转移。
            if dp[r] < 0 {
                continue
            }
            sum := dp[r] + num
            remainder := sum % 3
            if sum > next[remainder] {
                next[remainder] = sum
            }
        }
        dp = next
    }
    return dp[0]
}

复杂度分析

  • 时间复杂度：$O(n)$。每个元素只转移 3 个余数状态。
  • 空间复杂度：$O(1)$。dp 和 next 的长度固定为 3。

关键点总结

[!green]

  • 状态只保留余数与该余数下的最大和，把指数级子集压缩为 3 个槽位。
  • 同余状态中较大的和支配较小的和，这是状态可以合并的依据。
  • 快照不是写法偏好，而是保证「每个元素最多选一次」的 0-1 约束。
  • 空集使 dp[0] 从 0 开始，因此答案始终存在。

易错点总结

[!yellow]

  • 直接原地更新 dp：本轮产生的状态可能再次加入同一个 num，相当于重复使用元素。
  • 不跳过 -1 状态：不存在的子集会参与转移，产生虚假的候选和。
  • 只记录是否可达：题目要求最大和，同一余数必须保留数值最大的状态。
  • 返回三个状态中的最大值：最大值的余数未必是 0，最终只能返回 dp[0]。
  • 误用连续子数组方法：本题选择的是任意子集，元素位置没有连续性约束。

相似题目

题目 难度 关联与区别
1363. 形成三的最大倍数 困难 同样按模3分类并舍弃损失最小的元素，原题最大化拼成的整数，本题最大化元素和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63943299
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！