目标
一个魔法师有许多不同的咒语。
给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
每个咒语最多只能被使用 一次 。
请你返回这个魔法师可以达到的伤害值之和的 最大值 。
示例 1：
输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。示例 2：
输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。说明：
- 1 <= power.length <= 10^5
- 1 <= power[i] <= 10^9
思路
有一个数组 power 表示咒语的伤害值，魔法师使用其中任意咒语后，就无法再使用伤害值 +1 +2 -1 -2 的咒语，每个咒语只能使用一次，求伤害值的最大值。
使用哈希表记录伤害值相同的和，创建新数组（不包含重复伤害值），根据伤害值排序。如果不选当前伤害值，状态可以从后面转移而来，如果选则从后面大于当前伤害值 + 2 的转移而来。
代码
/**
* @date 2025-10-11 8:57
*/
public class MaximumTotalDamage3186 {
public long maximumTotalDamage(int[] power) {
Map<Integer, Long> sum = new HashMap<>();
for (int i : power) {
sum.merge(i, (long) i, Long::sum);
}
int n = sum.size();
int[] powers = new int[n];
int i = 0;
for (Integer damage : sum.keySet()) {
powers[i++] = damage;
}
Arrays.sort(powers);
long[] mem = new long[n + 1];
mem[n - 1] = sum.get(powers[n - 1]);
for (int j = n - 2; j >= 0; j--) {
int k = j;
while (k < n && powers[k] - powers[j] <= 2) {
k++;
}
mem[j] = Math.max(mem[j + 1], mem[k] + sum.get(powers[j]));
}
return mem[0];
}
}
性能
