We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Total Damage With Spell Casting

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each spell's damage has restrictions based on the values of adjacent spells (-2, -1, +1, +2).
  • The problem can be seen as a variant of the "House Robber" problem where adjacent spells cannot be selected.
  • We can use a frequency map to count occurrences of each damage value.
  • The strategy involves iterating through possible damage values and applying dynamic programming to maximize the total damage while respecting the casting restrictions.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the power array and m is the range of distinct damage values. Space Complexity: O(m), where m is the number of distinct damage values in the power array.

Solution

To solve the problem, we can use a dynamic programming approach. First, we will count the frequency of each damage value using a hash table. Then, we will iterate through the sorted unique damage values and maintain a dynamic programming array to track the maximum total damage. For each damage value, we will decide whether to include it in our total damage or not, based on the inclusion of previous values while avoiding the restricted ranges.

Code Solutions

def maxTotalDamage(power):
    from collections import Counter
    
    # Count frequency of each damage value
    damage_count = Counter(power)
    
    # Create a sorted list of unique damages
    unique_damages = sorted(damage_count.keys())
    
    # Initialize a dp array to store maximum damage at each step
    dp = {}
    
    # Iterate through unique damages
    for damage in unique_damages:
        # Calculate the maximum damage if including the current damage
        include_current = damage * damage_count[damage]
        if damage - 1 in dp:
            include_current += dp[damage - 1]
        if damage - 2 in dp:
            include_current = max(include_current, dp[damage - 2] + damage * damage_count[damage])
        
        # Update dp for the current damage
        dp[damage] = max(dp.get(damage - 1, 0), include_current)
    
    # The maximum total damage will be the last entry in dp
    return dp[unique_damages[-1]]
← Back to All Questions