Problem

A magician has various spells.

You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.

It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.

Each spell can be cast only once.

Return the maximum possible total damage that a magician can cast.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: power = [1,1,3,4]

Output: 6

Explanation:

The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with
damage 1, 1, 4.

Example 2

1
2
3
4
5
6
7
8
9


Input: power = [7,1,6,6]

Output: 13

Explanation:

The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with
damage 1, 6, 6.

Constraints

  • 1 <= power.length <= 10^5
  • 1 <= power[i] <= 10^9

Solution

Method 1 – Dynamic Programming with Frequency Counting

Intuition

This problem is similar to the “House Robber” or “Delete and Earn” pattern, but with a wider forbidden range. For each unique damage value, if we cast spells of this damage, we must skip all spells with damage within 2 of it. We use dynamic programming to track the best total damage at each value.

Approach

  1. Count the frequency of each damage value in power.
  2. Sort the unique damage values.
  3. Use a DP array where dp[i] is the max damage using up to the ith unique value:
    • For each value, either:
      • Skip it: take dp[i-1].
      • Take it: add its total damage to dp[j], where j is the last index with value at least 3 less than current.
  4. Return the last value in the DP array.

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting and DP over unique values.
  • 🧺 Space complexity: O(n) — For frequency and DP arrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        map<int, int> freq;
        for (int x : power) freq[x]++;
        vector<int> vals;
        for (auto& [v, _] : freq) vals.push_back(v);
        int n = vals.size();
        vector<long long> dp(n);
        for (int i = 0; i < n; ++i) {
            long long dmg = 1LL * vals[i] * freq[vals[i]];
            int j = i - 1;
            while (j >= 0 && vals[j] >= vals[i] - 2) --j;
            long long skip = (i ? dp[i-1] : 0LL);
            long long take = dmg + (j >= 0 ? dp[j] : 0LL);
            dp[i] = max(skip, take);
        }
        return dp.back();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func maximumTotalDamage(power []int) int64 {
    freq := map[int]int{}
    for _, x := range power { freq[x]++ }
    vals := []int{}
    for v := range freq { vals = append(vals, v) }
    sort.Ints(vals)
    n := len(vals)
    dp := make([]int64, n)
    for i, v := range vals {
        dmg := int64(v) * int64(freq[v])
        j := i - 1
        for j >= 0 && vals[j] >= v-2 { j-- }
        var skip int64 = 0
        if i > 0 { skip = dp[i-1] }
        var take int64 = dmg
        if j >= 0 { take += dp[j] }
        if skip > take { dp[i] = skip } else { dp[i] = take }
    }
    return dp[n-1]
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : power) freq.put(x, freq.getOrDefault(x, 0) + 1);
        List<Integer> vals = new ArrayList<>(freq.keySet());
        Collections.sort(vals);
        int n = vals.size();
        long[] dp = new long[n];
        for (int i = 0; i < n; ++i) {
            long dmg = 1L * vals.get(i) * freq.get(vals.get(i));
            int j = i - 1;
            while (j >= 0 && vals.get(j) >= vals.get(i) - 2) j--;
            long skip = i > 0 ? dp[i-1] : 0L;
            long take = dmg + (j >= 0 ? dp[j] : 0L);
            dp[i] = Math.max(skip, take);
        }
        return dp[n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maximumTotalDamage(power: IntArray): Long {
        val freq = mutableMapOf<Int, Int>()
        for (x in power) freq[x] = freq.getOrDefault(x, 0) + 1
        val vals = freq.keys.sorted()
        val n = vals.size
        val dp = LongArray(n)
        for (i in vals.indices) {
            val dmg = vals[i].toLong() * freq[vals[i]]!!.toLong()
            var j = i - 1
            while (j >= 0 && vals[j] >= vals[i] - 2) j--
            val skip = if (i > 0) dp[i-1] else 0L
            val take = dmg + if (j >= 0) dp[j] else 0L
            dp[i] = maxOf(skip, take)
        }
        return dp.last()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def maximumTotalDamage(power: list[int]) -> int:
    from collections import Counter
    freq = Counter(power)
    vals = sorted(freq)
    n = len(vals)
    dp = [0] * n
    for i, v in enumerate(vals):
        dmg = v * freq[v]
        j = i - 1
        while j >= 0 and vals[j] >= v - 2:
            j -= 1
        skip = dp[i-1] if i > 0 else 0
        take = dmg + (dp[j] if j >= 0 else 0)
        dp[i] = max(skip, take)
    return dp[-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn maximum_total_damage(power: Vec<i32>) -> i64 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for &x in &power { *freq.entry(x).or_insert(0) += 1; }
        let mut vals: Vec<_> = freq.keys().cloned().collect();
        vals.sort();
        let n = vals.len();
        let mut dp = vec![0i64; n];
        for i in 0..n {
            let dmg = vals[i] as i64 * freq[&vals[i]] as i64;
            let mut j = i as i32 - 1;
            while j >= 0 && vals[j as usize] >= vals[i] - 2 { j -= 1; }
            let skip = if i > 0 { dp[i-1] } else { 0 };
            let take = dmg + if j >= 0 { dp[j as usize] } else { 0 };
            dp[i] = skip.max(take);
        }
        dp[n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    maximumTotalDamage(power: number[]): number {
        const freq = new Map<number, number>();
        for (const x of power) freq.set(x, (freq.get(x) ?? 0) + 1);
        const vals = Array.from(freq.keys()).sort((a, b) => a - b);
        const n = vals.length;
        const dp = Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            const dmg = vals[i] * freq.get(vals[i])!;
            let j = i - 1;
            while (j >= 0 && vals[j] >= vals[i] - 2) --j;
            const skip = i > 0 ? dp[i-1] : 0;
            const take = dmg + (j >= 0 ? dp[j] : 0);
            dp[i] = Math.max(skip, take);
        }
        return dp[n-1];
    }
}