<p>A magician has various spells.</p>

<p>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.</p>

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

<p>Each spell can be cast <strong>only once</strong>.</p>

<p>Return the <strong>maximum</strong> possible <em>total damage</em> that a magician can cast.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

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

<p><strong>Explanation:</strong></p>

<p>The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

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

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

<p><strong>Explanation:</strong></p>

<p>The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= power.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= power[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        
        # sort based on power val
        # if val but there is no val - 1, val - 2, just pick up the max total from previous
        # if have val - 2 no val - 1 max(prev, dp[i - 2] + val)
        # if have val - 1 no val - 2 max(prev, dp[i - 2] + val)
        # if val - 1, val -2 both in max(dp[i - 1], dp[i - 2], dp[i - 3] + val)

        freq_dic = {}
        for val in power:
            freq_dic[val] = freq_dic.get(val, 0) + 1
        nums = []
        for val in freq_dic.keys():
            nums.append((val, freq_dic[val]))
        nums.sort()
        k = len(nums) # num of different val
        dp = [0 for _ in range(k)]
        dp[0] = nums[0][0] * nums[0][1] # init
        if k > 1:
            if nums[0][0] < nums[1][0] - 2:
                dp[1] = nums[1][0] * nums[1][1] + dp[0]
            else:
                dp[1] = max(nums[1][0] * nums[1][1], dp[0])
        for i in range(2, k):
            val, freq = nums[i]
            if nums[i - 1][0] < val - 2: # no val - 1, no val - 2
                dp[i] = dp[i - 1] + val * freq
            elif nums[i - 1][0] < val - 1: # has val - 2
                dp[i] = max(dp[i - 1], dp[i - 2] + val * freq)
            else: # has val - 1
                if nums[i - 2][0] < val - 2: # has val - 1 but not val - 2
                    dp[i] = max(dp[i - 1], dp[i - 2] + val * freq)
                else:
                    if i >= 3:
                        dp[i] = max(dp[i - 1], dp[i - 2], dp[i - 3] + val * freq)
                    else:
                        dp[i] = max(dp[i - 1], dp[i - 2], val * freq)
        print(dp)
        return max(dp)

43774