diff options
author | Jack Sangdahl <[email protected]> | 2025-10-10 21:45:49 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-10 21:45:49 -0600 |
commit | a5f938a020f2ddb10668e8d10a146027ea1807cd (patch) | |
tree | 29bb7777b7855919a9be47b3fd9b3f30d1f007ea /max_total_damage_spell_casting.py | |
parent | 24e6d065fa365234f842125c268e75aa17c31388 (diff) | |
download | leetcode-a5f938a020f2ddb10668e8d10a146027ea1807cd.tar.gz leetcode-a5f938a020f2ddb10668e8d10a146027ea1807cd.zip |
Diffstat (limited to 'max_total_damage_spell_casting.py')
-rw-r--r-- | max_total_damage_spell_casting.py | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/max_total_damage_spell_casting.py b/max_total_damage_spell_casting.py new file mode 100644 index 0000000..946bf15 --- /dev/null +++ b/max_total_damage_spell_casting.py @@ -0,0 +1,45 @@ +# 3186. Maximum Total Damage With Spell Casting +from collections import Counter + +""" +a magician has various spells. you are given an array 'power', 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 'power[i]', they cannot cast any spell with a damage of +'power[i] - 2', 'power[i] - 1', 'power[i] + 1', or 'power[i] + 2'. each spell +can only be cast once. return the maximum possible total damage that a +magician can cast. +""" + + +class Solution(object): + def maximumTotalDamage(self, power): + """ + :type power: List[int] + :rtype: int + """ + freq = Counter(power) + keys = sorted(freq) + n = len(keys) + dp = [0] * n + dp[0] = freq[keys[0]] * keys[0] + for i in range(1, n): + take = freq[keys[i]] * keys[i] + l, r, ans = 0, i - 1, -1 + while l <= r: + mid = (l + r) // 2 + if keys[mid] <= keys[i] - 3: + ans = mid + l = mid + 1 + else: + r = mid - 1 + if ans >= 0: + take += dp[ans] + dp[i] = max(dp[i - 1], take) + return dp[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumTotalDamage(power=[1, 1, 3, 4])) + print(obj.maximumTotalDamage(power=[7, 1, 6, 6])) |