aboutsummaryrefslogtreecommitdiff
path: root/taking_max_energy_mystic_dungeon.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-09 20:45:08 -0600
committerJack Sangdahl <[email protected]>2025-10-09 20:45:08 -0600
commit24e6d065fa365234f842125c268e75aa17c31388 (patch)
tree0d47ae857940f4d5d36602d7ac9009e1d136fcb0 /taking_max_energy_mystic_dungeon.py
parentb69b6266df7de0ab483d81ba6c9f5fa507aa8972 (diff)
downloadleetcode-24e6d065fa365234f842125c268e75aa17c31388.tar.gz
leetcode-24e6d065fa365234f842125c268e75aa17c31388.zip
3147. taking maximum energy from the mystic dungeon
Diffstat (limited to 'taking_max_energy_mystic_dungeon.py')
-rw-r--r--taking_max_energy_mystic_dungeon.py36
1 files changed, 36 insertions, 0 deletions
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))