LeetCode 1262. 可被三整除的最大和
题目描述
思路分析
解法一：动态规划（推荐）
核心思路：
- 定义
dp[r]表示当前遍历到的元素中，子集和对 3 取余为r（r = 0/1/2）时的最大子集和。- 初始化
dp[0] = 0，dp[1] = dp[2] = -∞（表示尚未达到该余数的合法状态）。- 遍历每个数
num，用临时数组保存更新前的状态，避免同一轮使用同一元素多次。- 对于当前元素
num，余数为r = num % 3，则更新：dp[(j + r) % 3] = max(dp[(j + r) % 3], dp[j] + num)，其中j为旧状态下合法的余数。- 遍历结束后，
dp[0]即为所求的最大可被 3 整除的子集和。
复杂度分析：
- 时间复杂度：O(n)，其中 n 表示数组 nums 的长度，每个元素只遍历一次，状态数固定为 3。
- 空间复杂度：O(1)，只使用了长度为 3 的 dp 数组。
class Solution {
public int maxSumDivThree(int[] nums) {
// dp[r] 表示子集和对 3 取余为 r 时的最大子集和，初始化为极小值
int[] dp = new int[]{0, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int num : nums) {
// 保存旧状态，防止同一轮更新被重复使用
int[] prev = dp.clone();
int r = num % 3;
for (int j = 0; j < 3; j++) {
// 仅从合法状态转移（跳过未达到的状态）
if (prev[j] == Integer.MIN_VALUE) {
continue;
}
// 加入当前元素后，新余数为 (j + r) % 3
int newR = (j + r) % 3;
dp[newR] = Math.max(dp[newR], prev[j] + num);
}
}
// dp[0] 即为可被 3 整除的最大子集和
return dp[0];
}
}
func maxSumDivThree(nums []int) int {
// dp[r] 表示子集和对 3 取余为 r 时的最大子集和
const minInf = -1 << 30
dp := [3]int{0, minInf, minInf}
for _, num := range nums {
// 保存旧状态，防止同一轮更新被重复使用
prev := dp
r := num % 3
for j := 0; j < 3; j++ {
// 仅从合法状态转移
if prev[j] == minInf {
continue
}
// 加入当前元素后，新余数为 (j + r) % 3
newR := (j + r) % 3
if prev[j]+num > dp[newR] {
dp[newR] = prev[j] + num
}
}
}
// dp[0] 即为可被 3 整除的最大子集和
return dp[0]
}
解法二：贪心
核心思路：
- 先求数组所有元素的总和
sum。- 若
sum % 3 == 0，直接返回sum。- 若
sum % 3 == 1，需要减少余数 1：
- 方案 A：移除一个余数为 1 的最小元素；
- 方案 B：移除两个余数为 2 的最小元素；
- 取两方案中结果更大的一个。
- 若
sum % 3 == 2，需要减少余数 2：
- 方案 A：移除一个余数为 2 的最小元素；
- 方案 B：移除两个余数为 1 的最小元素；
- 取两方案中结果更大的一个。
- 对每种余数只需记录最小的两个元素即可完成判断。
复杂度分析：
- 时间复杂度：O(n)，其中 n 表示数组 nums 的长度，遍历一次记录各余数的最小元素。
- 空间复杂度：O(1)，只需存储余数为 1 和 2 的最小两个元素。
class Solution {
public int maxSumDivThree(int[] nums) {
int sum = 0;
// rm1 存余数为 1 的最小两个元素，rm2 存余数为 2 的最小两个元素
int[] rm1 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] rm2 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
for (int num : nums) {
sum += num;
int r = num % 3;
// 维护余数为 1 的最小两个值
if (r == 1) {
if (num < rm1[0]) {
rm1[1] = rm1[0];
rm1[0] = num;
} else if (num < rm1[1]) {
rm1[1] = num;
}
}
// 维护余数为 2 的最小两个值
if (r == 2) {
if (num < rm2[0]) {
rm2[1] = rm2[0];
rm2[0] = num;
} else if (num < rm2[1]) {
rm2[1] = num;
}
}
}
if (sum % 3 == 0) {
return sum;
}
int ans = 0;
if (sum % 3 == 1) {
// 移除最小余数 1 的元素
if (rm1[0] != Integer.MAX_VALUE) {
ans = Math.max(ans, sum - rm1[0]);
}
// 移除最小的两个余数 2 的元素
if (rm2[1] != Integer.MAX_VALUE) {
ans = Math.max(ans, sum - rm2[0] - rm2[1]);
}
} else {
// 移除最小余数 2 的元素
if (rm2[0] != Integer.MAX_VALUE) {
ans = Math.max(ans, sum - rm2[0]);
}
// 移除最小的两个余数 1 的元素
if (rm1[1] != Integer.MAX_VALUE) {
ans = Math.max(ans, sum - rm1[0] - rm1[1]);
}
}
return ans;
}
}
func maxSumDivThree(nums []int) int {
sum := 0
// rm1 存余数为 1 的最小两个元素，rm2 存余数为 2 的最小两个元素
const maxInt = 1<<31 - 1
rm1 := [2]int{maxInt, maxInt}
rm2 := [2]int{maxInt, maxInt}
for _, num := range nums {
sum += num
r := num % 3
// 维护余数为 1 的最小两个值
if r == 1 {
if num < rm1[0] {
rm1[1] = rm1[0]
rm1[0] = num
} else if num < rm1[1] {
rm1[1] = num
}
}
// 维护余数为 2 的最小两个值
if r == 2 {
if num < rm2[0] {
rm2[1] = rm2[0]
rm2[0] = num
} else if num < rm2[1] {
rm2[1] = num
}
}
}
if sum%3 == 0 {
return sum
}
ans := 0
if sum%3 == 1 {
// 移除最小余数 1 的元素
if rm1[0] != maxInt {
if v := sum - rm1[0]; v > ans {
ans = v
}
}
// 移除最小的两个余数 2 的元素
if rm2[1] != maxInt {
if v := sum - rm2[0] - rm2[1]; v > ans {
ans = v
}
}
} else {
// 移除最小余数 2 的元素
if rm2[0] != maxInt {
if v := sum - rm2[0]; v > ans {
ans = v
}
}
// 移除最小的两个余数 1 的元素
if rm1[1] != maxInt {
if v := sum - rm1[0] - rm1[1]; v > ans {
ans = v
}
}
}
return ans
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1014. 最佳观光组合 | 中等 | 动态规划、数组 |
| 1524. 和为奇数的子数组数目 | 中等 | 动态规划、前缀和 |
| 1031. 两个非重叠子数组的最大和 | 中等 | 动态规划、前缀和 |
| 983. 最低票价 | 中等 | 动态规划 |
| 1049. 最后一块石头的重量 II | 中等 | 动态规划、背包 |
| 416. 分割等和子集 | 中等 | 动态规划、背包 |
| 2939. 最大异或乘积 | 中等 | 动态规划、贪心 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！