aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_total_damage_spell_casting.c42
-rw-r--r--max_total_damage_spell_casting.py45
-rw-r--r--taking_max_energy_mystic_dungeon.c35
-rw-r--r--taking_max_energy_mystic_dungeon.py36
4 files changed, 158 insertions, 0 deletions
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
+}
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]))
diff --git a/taking_max_energy_mystic_dungeon.c b/taking_max_energy_mystic_dungeon.c
new file mode 100644
index 0000000..1838d1a
--- /dev/null
+++ b/taking_max_energy_mystic_dungeon.c
@@ -0,0 +1,35 @@
+// 3147. Taking Maximum Energy From the Mystic Dungeon
+#include "leetcode.h"
+
+/*
+ * in a mystic dungeon, 'n' magicians are standing in a line. each magician has
+ * an attribute that gives you energe. some magicians can give you negative
+ * energy, which means taking energy from you. you have been cursed in such a
+ * way that after absorbing energy from magician 'i', you will be instantly
+ * transported to magician '(i + k)'. this process will be repeated until you
+ * reach the magician where '(i + k)' does not exist. in other words, you will
+ * choose a starting point until you reach the end of the magicians sequence,
+ * absorbing all the energy during the journey. you are given an array 'energy'
+ * and an integer 'k'. return the maximum possible energy you can gain. note
+ * that when you are reach a magician, you must take energy from them, whether
+ * it is positive or negative.
+ */
+
+int maximumEnergy(int *energy, int energySize, int k) {
+ int *dp = (int *)malloc(energySize * sizeof(int));
+ int ans = INT_MIN;
+ for (int i = energySize - 1; i >= 0; --i) {
+ int next = (i + k < energySize) ? dp[i + k] : 0;
+ dp[i] = energy[i] + next;
+ if (dp[i] > ans)
+ ans = dp[i];
+ }
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int e1[] = {5, 2, -10, -5, -1}, e2[] = {-2, -3, -1};
+ printf("%d\n", maximumEnergy(e1, ARRAY_SIZE(e1), 3)); // expect: 3
+ printf("%d\n", maximumEnergy(e2, ARRAY_SIZE(e2), 2)); // expect: -1
+}
diff --git a/taking_max_energy_mystic_dungeon.py b/taking_max_energy_mystic_dungeon.py
new file mode 100644
index 0000000..a4f39bd
--- /dev/null
+++ b/taking_max_energy_mystic_dungeon.py
@@ -0,0 +1,36 @@
+# 3147. Taking Maximum Energy From the Mystic Dungeon
+
+"""
+in a mystic dungeon, 'n' magicians are standing in a line. each magician has
+an attribute that gives you energe. some magicians can give you negative
+energy, which means taking energy from you. you have been cursed in such a
+way that after absorbing energy from magician 'i', you will be instantly
+transported to magician '(i + k)'. this process will be repeated until you
+reach the magician where '(i + k)' does not exist. in other words, you will
+choose a starting point until you reach the end of the magicians sequence,
+absorbing all the energy during the journey. you are given an array 'energy'
+and an integer 'k'. return the maximum possible energy you can gain. note
+that when you are reach a magician, you must take energy from them, whether
+it is positive or negative.
+"""
+
+
+class Solution(object):
+ def maximumEnergy(self, energy, k):
+ """
+ :type energy: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ans, n = float("-inf"), len(energy)
+ dp = [0] * n
+ for i in range(n - 1, -1, -1):
+ dp[i] = energy[i] + (dp[i + k] if i + k < n else 0)
+ ans = max(ans, dp[i])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumEnergy(energy=[5, 2, -10, -5, 1], k=3))
+ print(obj.maximumEnergy(energy=[-2, -3, -1], k=2))