LeetCode Daily Challenge P3186: Maximum Total Damage of Spell Casting

---

Timeline

Timeline

2025-10-11

init

Sliding Window + Dynamic Programming

---

Problem:

P3186 Maximum Total Damage of Spell Casting

https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/description/?envType=daily-question&envId=2025-10-11

Since there may be spells with the same damage, and if we choose multiple spells with the same damage, the total damage should add that damage multiplied by the number of spells with that damage. Therefore, we can first store the count of spells for each damage value, and then deduplicate power.
After deduplicating and sorting power, let f(i) represent the maximum total damage when choosing from the 0-th to i-th types of spells and finally choosing the i-th type. The state transition equation can be written as:

$$f[i] = \text{power}[i] + \max_{0\le j < i, \, power[j] \le power[i] - 2} f[j]$$

#include <algorithm>
#include <unordered_map>
#include <vector>

using std::unordered_map;
using std::vector;

class Solution {
    public:
        long long maximumTotalDamage(vector<int> &power)
        {
                // Let f(i) represent the maximum total damage when choosing from the 0-th to i-th types of spells and finally choosing the i-th type.
                // f(i) = max(f(j), j< i && power[j] < power[i]-2) + power[i] * mp[power[i]]
                int i, j, n;
                long long max = 0, ans = 0;
                unordered_map<long, long> count;

                for (int p : power) {
                        count[p]++;
                }

                // Deduplicate
                power.erase(std::unique(power.begin(), power.end()), power.end());
                // Sort
                std::sort(power.begin(), power.end());

                n = power.size();

                vector<long long> f(n, 0);
                f[0] = power[0] * count[power[0]];

                for (i = 1, j = 0; i < n; i++) {
                        while (j < i && power[j] < power[i] - 2) {
                                max = std::max(max, f[j]);
                                j++;
                        }
                        f[i] = max + power[i] * count[power[i]];
                }

                ans = *std::max_element(f.begin(), f.end());

                return ans;
        }
};