From a5f938a020f2ddb10668e8d10a146027ea1807cd Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Fri, 10 Oct 2025 21:45:49 -0600 Subject: 3186. maximum total damage with spell casting --- max_total_damage_spell_casting.c | 42 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) create mode 100644 max_total_damage_spell_casting.c (limited to 'max_total_damage_spell_casting.c') diff --git a/max_total_damage_spell_casting.c b/max_total_damage_spell_casting.c new file mode 100644 index 0000000..d229f6f --- /dev/null +++ b/max_total_damage_spell_casting.c @@ -0,0 +1,42 @@ +// 3186. Maximum Total Damage With Spell Casting +#include "leetcode.h" + +/* + * 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. + */ + +long long maximumTotalDamage(int *power, int powerSize) { + long long freq[100001] = {0}, dp[100001] = {0}; + for (int i = 0; i < powerSize; i++) + freq[power[i]]++; + int keys[100001], n = 0; + for (int i = 0; i <= 100000; i++) + if (freq[i]) + keys[n++] = i; + dp[0] = freq[keys[0]] * keys[0]; + for (int i = 1; i < n; i++) { + long long take = freq[keys[i]] * keys[i]; + int prev = -1; + for (int j = i - 1; j >= 0; j--) + if (keys[j] <= keys[i] - 3) { + prev = j; + break; + } + if (prev >= 0) + take += dp[prev]; + dp[i] = dp[i - 1] > take ? dp[i - 1] : take; + } + return dp[n - 1]; +} + +int main() { + int p1[] = {1, 1, 3, 4}, p2[] = {7, 1, 6, 6}; + printf("%lld\n", maximumTotalDamage(p1, ARRAY_SIZE(p1))); // expect: 6 + printf("%lld\n", maximumTotalDamage(p2, ARRAY_SIZE(p2))); // expect: 13 +} -- cgit v1.2.3