Maximum Total Damage With Spell Casting

main.md

Question

Approach

I group spells by damage and replace each damage x with a single weight total[x] = x * count(x). Because choosing damage x forbids x±1 and x±2, I can only combine damages that differ by at least 3. I sort the unique damage values and run a dynamic programming over that sorted list: for each index i with value vals[i], either skip it (carry dp[i-1]) or take total[vals[i]] plus the best dp from the largest index j with vals[j] ≤ vals[i] - 3. I find that j with bisect_right and use a prefix_max array for O(1) lookup of the best dp up to any index. The answer is the last dp value.

Implementation

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        if not power:
            return 0

        cnt = Counter(power)
        vals = sorted(cnt.keys())             
        total = [v * cnt[v] for v in vals]    

        m = len(vals)
        dp = [0] * m     
        prefix_max = [0] * m 

        for i in range(m):
            opt1 = dp[i-1] if i > 0 else 0

            need = vals[i] - 3
            j = bisect.bisect_right(vals, need) - 1
            opt2 = total[i] + (prefix_max[j] if j >= 0 else 0)

            dp[i] = max(opt1, opt2)
            prefix_max[i] = max(prefix_max[i-1] if i>0 else 0, dp[i])

        return dp[-1]

Complexities

• Time: O(n logn)
• Space: O(n)