Maximum Total Damage With Spell Casting

Language Options

Problem Description

Welcome to the world of spell casting, where you can deal maximum damage to your enemies while trying to avoid the awkwardness of casting the same spell too many times. Imagine you’re a wizard at a magical duel, and you have a set of spells with different power levels. However, there’s a catch! You can’t cast spells that are too similar in power back-to-back. It’s like trying to eat the same flavor of ice cream every day—eventually, you just want something different!

In this problem, you’re tasked with calculating the maximum total damage you can inflict using a list of spell powers, while adhering to the rule of not casting spells that are too close in power.

Code Solution


class Solution:
    def maximumTotalDamage(self, power: list[int]) -> int:
        count = collections.Counter(power)
        uniqueDamages = sorted(count.keys())
        dp = [[0] * 2 for _ in range(len(uniqueDamages))]

        for i, damage in enumerate(uniqueDamages):
            if i == 0:
                dp[0] = [0, damage * count[damage]]
                continue
            dp[i][0] = max(dp[i - 1])
            dp[i][1] = damage * count[damage]
            if i >= 1 and uniqueDamages[i - 1] not in (damage - 1, damage - 2):
                dp[i][1] += max(dp[i - 1])
            elif i >= 2 and uniqueDamages[i - 2] != damage - 2:
                dp[i][1] += max(dp[i - 2])
            elif i >= 3:
                dp[i][1] += max(dp[i - 3])

        return max(dp[-1])

Approach Explanation

The approach taken in this solution is dynamic programming. We maintain a 2D list dp where dp[i][0] represents the maximum damage we can achieve without using the i-th unique damage, and dp[i][1] represents the maximum damage when we do use it. The key is to ensure that we don’t use spells that are too close in power, which is handled by checking the previous damage values.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a party, and you have a selection of drinks (spells) to choose from. You can’t drink the same type of soda (spell) back-to-back because, well, that would just be boring! You want to maximize your enjoyment (damage) while ensuring you have a variety of flavors (powers). This problem is all about finding that perfect balance!