#3147

Medium

LeetCode Problem Workspace

Taking Maximum Energy From the Mystic Dungeon

Maximize your energy by strategically jumping through magicians using array and prefix sum techniques for optimal path calculation.

array prefix sum

Problem Statement

In a mystic dungeon, a line of magicians stands, each with an energy value that can be positive or negative. You are cursed such that after absorbing energy from magician i, you must teleport to magician (i + k) if it exists, continuing this process until no further jumps are possible. Your goal is to maximize total energy collected from this sequence.

Choose any starting magician and follow the teleportation rule of k jumps, summing energy values along the way. Determine the maximum total energy achievable from any starting point while accounting for negative values that could reduce the total energy.

Examples

Example 1

Input: energy = [5,2,-10,-5,1], k = 3

Output: 3

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

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

Solution Approach

Dynamic Programming with Jumps

Define dp[i] as the maximum energy starting from magician i. Calculate dp[i] by adding energy[i] to dp[i + k] if it exists, iterating from the end backwards. This captures the recursive energy gain efficiently.

Prefix Sum Optimization

Use prefix sums to quickly compute cumulative energy over jumps of size k. This avoids recalculating sums for overlapping paths and leverages the array plus prefix sum pattern to reduce redundant computation.

Selecting the Optimal Start

After computing dp for all indices, iterate through dp to find the maximum value. This ensures that the chosen starting magician yields the highest total energy, directly handling negative energy values in intermediate magicians.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each index is visited once in the backward dp computation, and space complexity is O(n) for storing the dp array. Prefix sums may reduce redundant sum calculations but do not increase asymptotic complexity.

What Interviewers Usually Probe

Check if candidate identifies dp[i] as the energy from index i including jumps.
Look for recognition that negative energy can lower total if path choice is wrong.
Candidate should optimize using array plus prefix sum rather than brute-force simulation.

Common Pitfalls or Variants

Common pitfalls

Failing to iterate from the end backward, causing dp values to be incorrect.
Ignoring negative energy and assuming all jumps add energy.
Recomputing sums for overlapping paths without using prefix sums.

Follow-up variants

Allowing variable jump sizes k[i] instead of a fixed k.
Modifying the dungeon so some magicians block teleportation to next jumps.
Changing the goal to minimize energy loss instead of maximizing gain.

FAQ

What is the core strategy for Taking Maximum Energy From the Mystic Dungeon?

Use dynamic programming with dp[i] as the maximum energy from index i and apply prefix sums to efficiently handle jumps of size k.

Can negative energy values be skipped?

No, teleportation forces visiting each k-th magician; dp accounts for negative values to select the best starting point.

How does prefix sum help in this problem?

Prefix sums allow rapid calculation of cumulative energy along jumps, reducing redundant summation and leveraging the array plus prefix sum pattern.

What is the time complexity for this approach?

Time complexity is O(n) since each index is processed once in the dp computation.

Is it better to start from the first magician?

Not necessarily; dp values show which starting index maximizes total energy, which could be any magician along the line.

terminal

Solution

Solution 1: Enumeration + Reverse Traversal

We can enumerate the endpoints within the range $[n - k, n)$, then traverse backwards from each endpoint, accumulating the energy values of wizards at intervals of $k$, and update the answer.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#3152 special array ii #3179 find the n th value after k seconds #3191 minimum operations to make binary array elements equal to one i