Welcome to Subscribe On Youtube
3147. Taking Maximum Energy From the Mystic Dungeon
Description
In a mystic dungeon, n
magicians are standing in a line. Each magician has an attribute that gives you energy. 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 and then teleport with k
jumps 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.
Example 1:
Input: energy = [5,2,10,5,1], k = 3
Output: 3
Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.
Example 2:
Input: energy = [2,3,1], k = 2
Output: 1
Explanation: We can gain a total energy of 1 by starting from magician 2.
Constraints:
1 <= energy.length <= 10^{5}
1000 <= energy[i] <= 1000
1 <= k <= energy.length  1
Solutions
Solution 1: Enumeration + Suffix Sum
We can enumerate the endpoint in the range of $[n  k, n)$, then start from the endpoint and traverse backwards, adding the energy value of the magician at each $k$ interval, and update the answer.
The time complexity is $O(n)$, where $n$ is the length of the array energy
. The space complexity is $O(1)$.

class Solution { public int maximumEnergy(int[] energy, int k) { int ans = (1 << 30); int n = energy.length; for (int i = n  k; i < n; ++i) { for (int j = i, s = 0; j >= 0; j = k) { s += energy[j]; ans = Math.max(ans, s); } } return ans; } }

class Solution { public: int maximumEnergy(vector<int>& energy, int k) { int ans = (1 << 30); int n = energy.size(); for (int i = n  k; i < n; ++i) { for (int j = i, s = 0; j >= 0; j = k) { s += energy[j]; ans = max(ans, s); } } return ans; } };

class Solution: def maximumEnergy(self, energy: List[int], k: int) > int: ans = inf n = len(energy) for i in range(n  k, n): j, s = i, 0 while j >= 0: s += energy[j] ans = max(ans, s) j = k return ans

func maximumEnergy(energy []int, k int) int { ans := (1 << 30) n := len(energy) for i := n  k; i < n; i++ { for j, s := i, 0; j >= 0; j = k { s += energy[j] ans = max(ans, s) } } return ans }

function maximumEnergy(energy: number[], k: number): number { const n = energy.length; let ans = Infinity; for (let i = n  k; i < n; ++i) { for (let j = i, s = 0; j >= 0; j = k) { s += energy[j]; ans = Math.max(ans, s); } } return ans; }