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 <= 105
-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)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|