---
# System prepended metadata

title: LC 3186. Maximum Total Damage With Spell Casting
tags: [medium, leedcode, DP, c++]

---

# 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<sup>5</sup></code>
- <code>1 <= power[i] <= 10<sup>9</sup></code>

## Solution 1 - DP
#### C++
```cpp=
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)一模一樣
