aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--taking_max_energy_mystic_dungeon.c35
-rw-r--r--taking_max_energy_mystic_dungeon.py36
2 files changed, 71 insertions, 0 deletions
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))