<p>A magician has various spells.</p>

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

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

<p>Each spell can be cast <strong>only once</strong>.</p>

<p>Return the <strong>maximum</strong> possible <em>total damage</em> that a magician can cast.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">power = [1,1,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">power = [7,1,6,6]</span></p>

<p><strong>Output:</strong> <span class="example-io">13</span></p>

<p><strong>Explanation:</strong></p>

<p>The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= power.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= power[i] &lt;= 10<sup>9</sup></code></li>
</ul>

# Data Structure: HashMap (for frequency count) and Memoization (cache) to store intermediate results
# Algorithm: Backtracking with caching to explore all possible decisions (cast or skip) and store results for subproblems

# Intuition:
# We need to maximize the total damage by deciding whether to cast or skip each spell.
# If we cast a spell with damage `x`, we must skip spells with damage `x ± 1` or `x ± 2` due to the problem's constraints.
# Use backtracking to try both "casting" and "skipping" each spell, but store the results of subproblems using memoization to avoid recalculating them.

# Detailed Intuition:
# 1. Count the frequency of each damage value using a HashMap.
# 2. Sort the unique damage values, as the restriction applies to spells with damage close to each other.
# 3. Use backtracking:
#    - At each unique damage value, choose whether to cast it or skip it.
#    - If you cast the current damage value, skip adjacent values.
#    - Cache the result for each starting index to avoid recalculating subproblems.
# 4. Use memoization to store the results of subproblems and avoid redundant computations.

# Pseudocode:
# 1. Count the frequency of each unique damage value using a HashMap.
# 2. Sort the unique damage values.
# 3. Implement a recursive backtracking function with caching.
#    - Base case: If the index goes beyond the list, return 0.
#    - Recursive case:
#      a. Skip the current spell and calculate the result for the next spell.
#      b. Cast the current spell, skip adjacent values, and calculate the result for the next valid spell.
# 4. Return the maximum result from the two options.

from collections import Counter

class Solution:
    def maximumTotalDamage(self, power):
        # Step 1: Count the frequency of each unique spell damage
        damage_count = Counter(power)
        
        # Step 2: Get all unique spell damages and sort them
        unique_damage = sorted(damage_count.keys())
        
        # Memoization cache to store intermediate results
        cache = {}
        
        # Backtracking function with memoization
        def backtrack(index):
            # Base case: If the index is out of bounds, return 0
            if index >= len(unique_damage):
                return 0
            
            # Check if result is already cached
            if index in cache:
                return cache[index]
            
            # Current damage value and its total contribution (damage * frequency)
            current_damage = unique_damage[index]
            current_contribution = current_damage * damage_count[current_damage]
            
            # Option 1: Skip the current spell
            option1 = backtrack(index + 1)
            
            # Option 2: Cast the current spell and skip adjacent values (x ± 1, x ± 2)
            next_index = index + 1
            while next_index < len(unique_damage) and unique_damage[next_index] <= current_damage + 2:
                next_index += 1
            
            option2 = current_contribution + backtrack(next_index)
            
            # Cache the result and return the maximum of both options
            cache[index] = max(option1, option2)
            return cache[index]
        
        # Step 4: Start the backtracking from index 0
        return backtrack(0)

# Time Complexity: O(n), where n is the number of unique damage values. Each unique damage value is processed once, and the memoization ensures no redundant calculations.
# Space Complexity: O(n), due to the space used by the frequency map, cache, and recursion stack.

178976