Maximum Total Damage With Spell Casting

• Create a frequency map of the power array to count occurrences of each spell damage.
• Extract the unique damage values into a list and sort them in ascending order. Let this be uniquePowers.
• Define a recursive function, solve(index), which computes the maximum damage from uniquePowers starting from index.
• Base Case: If index is out of bounds (>= uniquePowers.length), return 0.
• Recursive Step: For the spell at uniquePowers[index], there are two choices:
  1. Skip: Don't cast this spell. The damage is solve(index + 1).
  2. Cast: Cast this spell. The damage is (uniquePowers[index] * frequency). We then find the next non-conflicting spell. This is the first spell uniquePowers[nextIndex] such that uniquePowers[nextIndex] > uniquePowers[index] + 2. The total damage for this choice is (current spell's damage) + solve(nextIndex).
• The function returns the maximum of the 'Skip' and 'Cast' options.
• The initial call is solve(0).

The core idea is to simplify the problem first. Since the constraint depends on the damage value, not the spell's index, we can group spells by their power. If we decide to cast a spell with power p, it's always optimal to cast all spells with power p to maximize damage without adding new restrictions.

1. Preprocessing: We first count the frequencies of each power value using a HashMap. Then, we extract the unique power values and sort them. This gives us a sorted array of unique powers, say uniquePowers.

2. Recursion: We define a recursive function solve(index) that calculates the maximum damage possible from the spells in uniquePowers from index to the end. At each index, we face a choice:

   • Skip uniquePowers[index]: We move to the next unique power, so the damage is solve(index + 1).
   • Cast uniquePowers[index]: We gain uniquePowers[index] * count damage. Due to the constraint, we cannot cast spells with power p+1 or p+2. We must find the next available spell, which is the first one with power greater than uniquePowers[index] + 2. Let its index be nextIndex. We then add the result of solve(nextIndex).

The function returns the maximum of these two outcomes. This method explores the entire search space, leading to a correct but very slow solution.

1import java.util.*;2 3class Solution {4    private Map<Integer, Integer> counts;5    private int[] uniquePowers;6 7    public long maximumTotalDamage(int[] power) {8        counts = new HashMap<>();9        for (int p : power) {10            counts.put(p, counts.getOrDefault(p, 0) + 1);11        }12 13        uniquePowers = new int[counts.size()];14        int i = 0;15        for (int p : counts.keySet()) {16            uniquePowers[i++] = p;17        }18        Arrays.sort(uniquePowers);19 20        return solve(0);21    }22 23    private long solve(int index) {24        if (index >= uniquePowers.length) {25            return 0;26        }27 28        // Option 1: Skip current power29        long damageSkip = solve(index + 1);30 31        // Option 2: Take current power32        long currentPower = uniquePowers[index];33        long currentDamage = currentPower * counts.get((int)currentPower);34 35        // Find the next index to jump to36        int nextIndex = index + 1;37        while (nextIndex < uniquePowers.length && uniquePowers[nextIndex] <= currentPower + 2) {38            nextIndex++;39        }40        long damageTake = currentDamage + solve(nextIndex);41 42        return Math.max(damageSkip, damageTake);43    }44}