Skip to content

3437. Maximum Total Damage With Spell Casting

Array Hash Table Two Pointers Binary Search Dynamic Programming Sorting Counting

Problem - Maximum Total Damage With Spell Casting

Medium

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.

 

Example 1:

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:

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 <= 105
  • 1 <= power[i] <= 109

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        n = len(power)
        count = Counter(power)
        power.sort()

        next_spell_index = [bisect_right(power, val + 2, lo=i + 1) for i, val in enumerate(power)]

        @cache
        def dfs(i):
            if i >= n:
                return 0
            val1 = dfs(i + count[power[i]])
            val2 = power[i] * count[power[i]] + dfs(next_spell_index[i])
            return max(val1, val2)

        return dfs(0)

Submission Stats:

  • Runtime: 931 ms (15.75%)
  • Memory: 251.9 MB (5.00%)