3147. Taking Maximum Energy From the Mystic Dungeon

Problem Description

In a mystic dungeon, n magicians are standing in a line. Each magician has an attribute that gives you energy, which could be negative or positive. After absorbing energy from magician i, you will be instantly transported to magician (i + k). This process is repeated until you reach a point where no further jump (i + k) is possible.

The task is to choose a starting point and teleport with k jumps, absorbing all the energy values during the journey. You need to find out the maximum possible energy you can accumulate from such a journey.

Intuition

The intuitive solution to this problem involves backtracking from potential endpoints. We recognize that the journey must end at one of the last k magicians since any journey must fit into the bounds of the array energy.

We can approach solving this by starting from potential endpoints in the range [n - k, n) and working backwards through the array. For each starting point in this range, we iterate backward, adding up the energy values at intervals of k. During this backward iteration, we keep a running sum of the energy values and check if the current sum is the maximum energy obtained so far. This method optimally utilizes the given teleportation mechanic, ensuring all possible paths starting within the defined range are covered.

Learn more about Prefix Sum patterns.

Solution Approach

The solution employs a combination of enumeration and suffix sum calculation. Here’s a step-by-step breakdown:

Initialize Variables:
- Set ans to negative infinity (-inf) to ensure that any calculated sum will be larger initially.
- Determine n, the length of the energy array.
Enumerate Endpoints:
- Iterate over indices in the range [n - k, n), considering each one as a potential endpoint of the journey. The end index is chosen from this range since beginning from any index sooner would require more jumps than possible to reach the end.
Calculate Sums Backward:
- For each starting index i, initialize j with i and a cumulative sum s starting at 0.
- Perform a backward iteration where, for every j, the energy at index j is added to s.
- Update ans with the maximum of the current s and the previously calculated ans.
- Decrement j by k for each iteration to simulate the teleport jump backward.
Return Result:
- After evaluating all possible starts in the defined range, ans, which holds the maximum energy accumulated through a valid path, is returned.

This approach effectively uses backward enumeration to ensure the most energy is accumulated by leveraging the given teleportation constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple case where we have a list of magicians with energy values: [3, -5, 7, 2, 8, -10] and k = 2.

Step-by-Step Execution:

Initialize Variables:
- ans is set to -inf initially.
- n is calculated as 6 (the length of the energy array).
Enumerate Endpoints:
- Since n = 6 and k = 2, the possible endpoints to consider are indices 4 and 5.
Calculate Sums Backward:

Starting at Endpoint 4:
- Initialize j = 4 and cumulative s = 0.
- Add energy[4] (which is 8) to s, updating s = 8.
- Compare s with ans, and since 8 > -inf, update ans = 8.
- Decrement j by k (2), resulting in j = 2.
- Add energy[2] (which is 7) to s, updating s = 15.
- Compare s with ans, and since 15 > 8, update ans = 15.
- Decrement j by k again, resulting in j = 0.
- Add energy[0] (which is 3) to s, updating s = 18.
- Compare s with ans, and since 18 > 15, update ans = 18.
- Decrement j to -2, which is out of bounds, stopping this backward iteration.
Starting at Endpoint 5:
- Initialize j = 5 and cumulative s = 0.
- Add energy[5] (which is -10) to s, updating s = -10.
- Compare s with ans, and since 18 > -10, ans remains 18.
- Decrement j by k (2), resulting in j = 3.
- Add energy[3] (which is 2) to s, updating s = -8.
- Compare s with ans, ans remains 18.
- Decrement j by k again, resulting in j = 1.
- Add energy[1] (which is -5) to s, updating s = -13.
- Compare s with ans, and ans remains 18.
- Decrement j to -1, out of bounds, ending this backward iteration.
Return Result:
- Finally, return ans, which is 18, as the maximum accumulated energy.

The algorithm effectively navigates the teleportation constraints to determine that starting at index 4 and teleporting backward to indices 4 -> 2 -> 0, accumulates the maximum energy 18.

Solution Implementation

1from typing import List
2import math
3
4class Solution:
5    def maximumEnergy(self, energy: List[int], k: int) -> int:
6        # Initialize the result to negative infinity to ensure any sum will be larger initially
7        ans = -math.inf
8        n = len(energy)
9      
10        # Iterate over the last k elements in the energy list
11        for i in range(n - k, n):
12            j, current_sum = i, 0
13          
14            # Calculate the sum of elements by stepping backwards by k indices
15            while j >= 0:
16                # Add current energy value to current_sum
17                current_sum += energy[j]
18              
19                # Update the maximum energy sum
20                ans = max(ans, current_sum)
21              
22                # Move j k steps backwards
23                j -= k
24      
25        # Return the maximum sum found
26        return ans
27

1class Solution {
2    public int maximumEnergy(int[] energy, int k) {
3        // Initialize the maximum answer to a very low number.
4        int maxEnergy = Integer.MIN_VALUE; 
5        int n = energy.length;
6      
7        // Loop over the last 'k' elements of the array.
8        for (int i = n - k; i < n; ++i) {
9            // Start another loop to potentially traverse the array backwards in steps of 'k'.
10            for (int j = i, currentSum = 0; j >= 0; j -= k) {
11                // Add the current energy value to the sum.
12                currentSum += energy[j];
13              
14                // Update the maximum energy if the current sum is greater.
15                maxEnergy = Math.max(maxEnergy, currentSum);
16            }
17        }
18      
19        // Return the maximum sum found.
20        return maxEnergy;
21    }
22}
23

1class Solution {
2public:
3    int maximumEnergy(vector<int>& energy, int k) {
4        int ans = -(1 << 30); // Initialize answer to a very small number, effectively negative infinity
5        int n = energy.size(); // Get the size of the energy vector
6
7        // Iterate over the last k elements of the vector
8        for (int i = n - k; i < n; ++i) {
9            // For each starting position i, initialize sum s to 0
10            for (int j = i, s = 0; j >= 0; j -= k) {
11                s += energy[j]; // Accumulate the energy values at intervals of k
12                ans = std::max(ans, s); // Update ans with the maximum sum encountered
13            }
14        }
15        return ans; // Return the maximum energy sum found
16    }
17};
18

1// Function to calculate the maximum energy accumulated
2// by jumping back k indices in the energy array.
3function maximumEnergy(energy: number[], k: number): number {
4    const n = energy.length; // The length of the energy array
5    let ans = -Infinity; // Initialize the answer to negative infinity
6  
7    // Iterate from the (n-k)th to the last element in the energy array
8    for (let i = n - k; i < n; ++i) {
9        let s = 0; // To store the sum of the selected energies
10      
11        // Move from index i backwards in steps of k
12        for (let j = i; j >= 0; j -= k) {
13            s += energy[j]; // Accumulate energy value
14            ans = Math.max(ans, s); // Update the maximum energy sum found
15        }
16    }
17  
18    return ans; // Return the maximum energy collected
19}
20

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array energy. For each of the last k elements, the while loop iterates backwards in steps of k, potentially covering every element once.

The space complexity of the code is O(1), as it uses a constant amount of extra space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems