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}

• Preprocess the power array to get a frequency map and a sorted array of uniquePowers.
• Create a memoization table, memo, of the same size as uniquePowers, initialized to a sentinel value (e.g., -1).
• Use the same recursive function solve(index) as in the brute-force approach.
• Before any computation in solve(index), check if memo[index] already has a computed value. If so, return it immediately.
• If not, compute the result for the 'Skip' and 'Cast' options.
• To find the nextIndex for the 'Cast' option efficiently, use binary search on the uniquePowers array. This finds the next non-conflicting spell in O(log M) time.
• Store the computed result in memo[index] before returning it.

The problem exhibits optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The recursive brute-force approach is inefficient because it re-calculates solve(k) for the same k multiple times through different recursive paths.

We can eliminate this redundant work by storing the result of solve(index) the first time it's computed. A memo array (or a HashMap) can be used for this. memo[index] will store the result of solve(index).

The logic is as follows:

1. Inside solve(index), first check if memo[index] contains a valid result. If yes, return it.
2. If not, proceed with the regular recursive calculation: find the max damage by either skipping or casting the spell at uniquePowers[index].
3. To make the 'Cast' option efficient, we need to quickly find the next non-conflicting spell. Instead of a linear scan, we can use binary search on the sorted uniquePowers array to find the first power greater than currentPower + 2. This reduces the time for this step from O(M) to O(log M).
4. Once the result is computed, store it in memo[index] before returning.

This ensures that each subproblem solve(index) is computed only once.

1import java.util.*;2 3class Solution {4    private Map<Integer, Integer> counts;5    private int[] uniquePowers;6    private long[] memo;7 8    public long maximumTotalDamage(int[] power) {9        counts = new HashMap<>();10        for (int p : power) {11            counts.put(p, counts.getOrDefault(p, 0) + 1);12        }13 14        uniquePowers = new int[counts.size()];15        int i = 0;16        for (int p : counts.keySet()) {17            uniquePowers[i++] = p;18        }19        Arrays.sort(uniquePowers);20        21        memo = new long[uniquePowers.length];22        Arrays.fill(memo, -1);23        return solve(0);24    }25 26    private long solve(int index) {27        if (index >= uniquePowers.length) {28            return 0;29        }30        if (memo[index] != -1) {31            return memo[index];32        }33 34        // Option 1: Skip current power35        long damageSkip = solve(index + 1);36 37        // Option 2: Take current power38        long currentPower = uniquePowers[index];39        long currentDamage = currentPower * counts.get((int)currentPower);40 41        // Find the next non-conflicting index using binary search42        int low = index + 1, high = uniquePowers.length - 1;43        int nextIndex = uniquePowers.length;44        while (low <= high) {45            int mid = low + (high - low) / 2;46            if (uniquePowers[mid] > currentPower + 2) {47                nextIndex = mid;48                high = mid - 1;49            } else {50                low = mid + 1;51            }52        }53 54        long damageTake = currentDamage + solve(nextIndex);55 56        memo[index] = Math.max(damageSkip, damageTake);57        return memo[index];58    }59}

• Perform the same preprocessing: create a frequency map and a sorted array uniquePowers of size M.
• Create a DP array, dp, of size M. dp[i] will store the maximum damage considering spells up to uniquePowers[i].
• Iterate from i = 0 to M-1 to fill the dp array.
• For each i, calculate the max damage by considering two choices for uniquePowers[i]:
  1. Skip: The max damage is the result from the previous state, dp[i-1] (or 0 if i=0).
  2. Cast: The damage is (uniquePowers[i] * frequency). To this, we add the max damage from non-conflicting previous spells. This requires finding the result for the largest power uniquePowers[j] such that uniquePowers[j] < uniquePowers[i] - 2. This corresponds to dp[j].
• The value dp[i] is the maximum of these two choices.
• The index j can be found efficiently using a two-pointer approach. Maintain a pointer j that tracks the last non-conflicting state. As i increases, j only moves forward, leading to an O(M) DP calculation.
• The final answer is dp[M-1].

An iterative DP approach is often preferred for its performance and avoidance of recursion limits. We build a dp array where dp[i] represents the maximum total damage achievable by considering the first i+1 unique spell powers (i.e., from uniquePowers[0] to uniquePowers[i]).

1. Preprocessing: As before, we get the sorted uniquePowers array and their frequencies.

2. DP State: dp[i] = Maximum damage using a subset of {uniquePowers[0], ..., uniquePowers[i]}.

3. DP Transition: We iterate i from 0 to M-1 and compute dp[i]:

   • Choice 1 (Skip uniquePowers[i]): If we don't cast this spell, the maximum damage is whatever we could achieve with the previous spells. This is simply dp[i-1] (if i > 0).
   • Choice 2 (Cast uniquePowers[i]): We gain uniquePowers[i] * count damage. We must add the maximum damage from spells that don't conflict. We need to find the maximum damage from the subproblem ending just before the conflicting range, i.e., from spells with power < uniquePowers[i] - 2. This corresponds to dp[j] where uniquePowers[j] is the largest power satisfying this condition.

   The recurrence is dp[i] = max(damage_if_skip, damage_if_cast). Finding the index j for each i can be done with a binary search (O(M log M)) or, even better, a two-pointer technique (O(M)), as the required j is non-decreasing as i increases.

1import java.util.*;2 3class Solution {4    public long maximumTotalDamage(int[] power) {5        if (power == null || power.length == 0) {6            return 0;7        }8 9        Map<Integer, Integer> counts = new HashMap<>();10        for (int p : power) {11            counts.put(p, counts.getOrDefault(p, 0) + 1);12        }13 14        int[] uniquePowers = new int[counts.size()];15        int i = 0;16        for (int p : counts.keySet()) {17            uniquePowers[i++] = p;18        }19        Arrays.sort(uniquePowers);20 21        int m = uniquePowers.length;22        long[] dp = new long[m];23        24        int j = 0; // Two-pointer for finding previous non-conflicting state25        for (i = 0; i < m; i++) {26            long currentPower = uniquePowers[i];27            long currentTotalDamage = currentPower * counts.get((int)currentPower);28 29            // Move pointer j forward. It will point to the first power that is >= currentPower - 2.30            while (uniquePowers[j] < currentPower - 2) {31                j++;32            }33            34            // The last valid subproblem result is at dp[j-1]35            long prevDamage = (j > 0) ? dp[j - 1] : 0;36            long damageTake = currentTotalDamage + prevDamage;37 38            // Option to skip the current power39            long damageSkip = (i > 0) ? dp[i - 1] : 0;40 41            dp[i] = Math.max(damageTake, damageSkip);42        }43 44        return m > 0 ? dp[m - 1] : 0;45    }46}