diff options
author | Jack Sangdahl <[email protected]> | 2025-10-09 20:45:08 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-09 20:45:08 -0600 |
commit | 24e6d065fa365234f842125c268e75aa17c31388 (patch) | |
tree | 0d47ae857940f4d5d36602d7ac9009e1d136fcb0 /taking_max_energy_mystic_dungeon.py | |
parent | b69b6266df7de0ab483d81ba6c9f5fa507aa8972 (diff) | |
download | leetcode-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.py | 36 |
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)) |