# LC 3186. Maximum Total Damage With Spell Casting

### [Problem link](https://leetcode.com/problems/maximum-total-damage-with-spell-casting/)

###### tags: `leedcode` `medium` `c++` `DP`

A magician has various spells.

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.

It is a known fact that if a magician decides to cast a spell with a damage of <code>power[i]</code>, they **cannot** 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>.

Each spell can be cast **only once** .

Return the **maximum** possible total damage that a magician can cast.

**Example 1:**

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

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

Explanation:

The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.

**Example 2:**

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

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

Explanation:

The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.

**Constraints:**

- <code>1 <= power.length <= 10⁵</code>
- <code>1 <= power[i] <= 10⁹</code>

## Solution 1 - DP
#### C++

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> umap;
        for (int& p: power) {
            umap[p]++;
        }

        vector<pair<int, int>> a(umap.begin(), umap.end());
        sort(a.begin(), a.end());
        int n = a.size();
        vector<long long> dp(n + 1, 0);
        for (int i = 0; i < n; i++) {
            auto& [p, cnt] = a[i];
            int j = i;
            while (j > 0 && a[j - 1].first >= p - 2) {
                j--;
            }
            dp[i + 1] = max(dp[i], dp[j] + (long long)p * cnt);
        }
        return dp.back();
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(n) |

## Note
跟[LC 740. Delete and Earn](https://hackmd.io/@Alone0506/HJ2p_Zhr0)一模一樣