<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>

from collections import defaultdict
from bisect import bisect_left

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        #blacklist = defaultdict(lambda: 0)
        power = sorted(power)
        last_idx = {}
        for i, pwr in enumerate(power):
            last_idx[pwr] = i

        n = len(power)
        dp = [[0,0] for _ in range(n)]
        dp[n-1][1] = power[n-1]
        dp[n-1][0] = 0

        for i in range(n-2, -1, -1):

            l_idx = last_idx[power[i]]
            factor = (l_idx - i + 1)

            dpi1 = power[i] * factor
            
            #j = l_idx
            j = bisect_left(power, power[i] + 3, l_idx)
            #while j < n and (power[j] <= (power[i] + 2)):
            #    j += 1
            dpi1 = max(dpi1, dp[j][0] + dpi1, dp[j][1] + dpi1) if j < n else dpi1
            
            dp[i][1] = dpi1

            # or we don't
            dpi0 = max(dp[i+1][0], dp[i+1][1])
            dp[i][0] = dpi0

        #print(dp)
        return max(dp[0][0], dp[0][1])

        """def walk(i, damage):
            if i == len(power):
                return damage

            if blacklist[power[i]] > 0:
                # we can't cast this spell.
                return walk(i+1, damage)

            # we can cast this spell
            notPick = walk(i+1, damage)

            update_blacklist(i, True)
            pick = walk(i+1, damage + power[i])
            update_blacklist(i, False)

            return max(pick, notPick)

        def update_blacklist(i, add):
            delta = 1 if add else -1
            blacklist[power[i]-2] += delta
            blacklist[power[i]-1] += delta
            blacklist[power[i]+1] += delta
            blacklist[power[i]+2] += delta

        return walk(0, 0)"""
48781