# Taking Maximum Energy From the Mystic Dungeon
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon)
Canonical: https://scaleengineer.com/dsa/problems/taking-maximum-energy-from-the-mystic-dungeon
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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.

**Note** that when you are reach a magician, you _must_ take energy from them, whether it is negative or positive energy.

**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`

​​​​​​

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We consider every possible magician from index `0` to `n-1` as a starting point. For each starting point, we calculate the total energy by following the path of jumps of size `k` and summing the energy values until we go past the end of the line of magicians. We maintain a variable to keep track of the maximum energy found so far across all paths.
**Time:** O(N * N/k). The outer loop runs `N` times (where `N` is `energy.length`). The inner `while` loop's iterations depend on the starting point `i` and `k`, running about `(N-i)/k` times. In the worst-case scenario (e.g., `k=1`), the complexity approaches O(N^2). · **Space:** O(1), as we only use a few variables to store the current and maximum energy, regardless of the input size.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Uses constant extra space.
**Cons:** Highly inefficient for large inputs, especially when `k` is small.; Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The algorithm works as follows:

1.  Initialize a variable `maxEnergy` to the smallest possible integer value to ensure any calculated energy will be greater.
2.  Loop through each index `i` from `0` to `n-1`. Each `i` represents a potential starting point for our journey.
3.  Inside this loop, for each starting index `i`, initialize a `currentEnergy` variable to `0`.
4.  Start another loop or a simulation process with a pointer `j`, initialized to `i`.
5.  This inner loop continues as long as `j` is a valid index (i.e., `j < n`). In each step of this inner loop, we add the energy of the magician at `energy[j]` to `currentEnergy` and then update `j` by adding `k` to it, simulating the teleportation.
6.  Once the inner loop finishes (meaning we've jumped out of bounds), `currentEnergy` holds the total energy for the path that started at `i`.
7.  We then compare `currentEnergy` with `maxEnergy` and update `maxEnergy` if `currentEnergy` is larger.
8.  After the outer loop has finished checking all possible starting points from `0` to `n-1`, the `maxEnergy` variable will hold the maximum possible energy that can be gained, which is our answer.

```java
class Solution {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        int maxEnergy = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int currentEnergy = 0;
            int j = i;
            while (j < n) {
                currentEnergy += energy[j];
                j += k;
            }
            if (currentEnergy > maxEnergy) {
                maxEnergy = currentEnergy;
            }
        }
        return maxEnergy;
    }
}
```
### Algorithm
*   Initialize a variable `maxEnergy` to a very small number (e.g., `Integer.MIN_VALUE`).
*   Iterate through each index `i` from `0` to `n-1` to consider it as a starting point.
*   For each `i`, initialize `currentEnergy = 0`.
*   Start a simulation from `j = i`. While `j` is a valid index (`j < n`):
    *   Add `energy[j]` to `currentEnergy`.
    *   Update `j` to `j + k`.
*   After the simulation for `i` is done, update `maxEnergy = max(maxEnergy, currentEnergy)`.
*   Return `maxEnergy` after checking all starting points.

## Dynamic Programming with Extra Space
The brute-force approach involves redundant calculations. The total energy from a path starting at `i` is simply `energy[i]` plus the total energy from the path starting at `i+k`. This property of overlapping subproblems and optimal substructure is a perfect fit for dynamic programming. We can define `dp[i]` as the total energy gained starting from magician `i`. The recurrence relation is `dp[i] = energy[i] + dp[i+k]`. Since `dp[i]` depends on a value at a larger index (`i+k`), we should compute the `dp` values by iterating backward from the end of the array.
**Time:** O(N). We perform a single pass backward to fill the `dp` array (`O(N)`) and another pass to find the maximum value in it (`O(N)`). This results in a total linear time complexity. · **Space:** O(N), where `N` is the length of the `energy` array. This is due to the extra `dp` array we use to store the results.
**Pros:** Efficient time complexity, making it suitable for large inputs.; Avoids redundant calculations present in the brute-force method.
**Cons:** Requires extra space proportional to the input size, which could be an issue for very large inputs in memory-constrained systems.
### Explanation
This approach uses a DP table to store the results of subproblems to avoid re-computation.

1.  We create an auxiliary array, `dp`, of the same size as the `energy` array. `dp[i]` will store the total energy of a path that begins at index `i`.
2.  We iterate backward through the `energy` array, from index `i = n-1` down to `0`.
3.  For each index `i`, we compute `dp[i]` based on our recurrence relation:
    *   The next magician in the sequence would be at index `i + k`.
    *   If `i + k` is outside the array bounds (`>= n`), it means the path starting at `i` has only one magician. Thus, `dp[i] = energy[i]`.
    *   If `i + k` is a valid index, the total energy is the sum of the current magician's energy and the total energy from the rest of the path. Since we are iterating backward, the value for the path starting at `i+k` has already been computed and stored in `dp[i+k]`. Therefore, `dp[i] = energy[i] + dp[i+k]`.
4.  After the loop completes, the `dp` array is fully populated, with each `dp[i]` holding the total energy for a path starting at `i`. The final answer is the maximum value found within this `dp` array.

```java
class Solution {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        int[] dp = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            if (i + k >= n) {
                dp[i] = energy[i];
            } else {
                dp[i] = energy[i] + dp[i + k];
            }
        }

        int maxEnergy = Integer.MIN_VALUE;
        for (int totalEnergy : dp) {
            if (totalEnergy > maxEnergy) {
                maxEnergy = totalEnergy;
            }
        }
        return maxEnergy;
    }
}
```
### Algorithm
*   Create a `dp` array of size `n`.
*   Iterate backward from `i = n-1` down to `0`.
*   For each `i`, calculate `dp[i]` using the recurrence: 
    *   If `i + k >= n`, then `dp[i] = energy[i]`.
    *   If `i + k < n`, then `dp[i] = energy[i] + dp[i+k]`.
*   After filling the `dp` array, find the maximum value in it. This maximum value is the answer.

## Optimized Dynamic Programming (In-place)
This approach builds upon the dynamic programming solution by optimizing its space complexity. Observing the DP recurrence `dp[i] = energy[i] + dp[i+k]`, we see that to compute the value for index `i`, we only need the value at index `i+k`. Since our backward iteration ensures that the value for `i+k` is computed before `i`, we don't need a separate `dp` array. We can reuse the input `energy` array itself to store the DP values, effectively performing the computation in-place.
**Time:** O(N). The solution involves two separate passes over the array: one to update the values in-place and another to find the maximum. Both are linear operations, resulting in an overall `O(N)` time complexity. · **Space:** O(1). The algorithm modifies the input array in-place and does not require any additional data structures that scale with the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1), making it very memory-efficient.; It is the most efficient solution for this problem.
**Cons:** This approach modifies the input array. If the original array must be preserved, a copy should be made first, which would negate the space optimization.
### Explanation
The in-place dynamic programming approach refines the previous method by eliminating the need for an extra array.

1.  Instead of creating a new `dp` array, we use the input `energy` array to store the total path sums. The goal is to transform `energy` such that `energy[i]` will hold the total energy for a path starting at index `i`.
2.  We iterate backward through the `energy` array, from `i = n-1` down to `0`.
3.  For each index `i`, we check if a jump from this position is possible. If `i + k < n`, it means the path continues. The value at `energy[i+k]` has, at this point in the backward iteration, already been updated to represent the total energy of the path starting from `i+k`. We can therefore update the current element by adding this pre-calculated sum: `energy[i] = energy[i] + energy[i+k]`.
4.  If `i + k >= n`, the path starts and ends at `i`, so `energy[i]` already represents the total sum for this path, and no action is needed.
5.  After this loop finishes, the `energy` array is fully updated. The value at each index `i` is now the total energy for a path starting at that index.
6.  A final pass through the modified `energy` array is made to find the maximum value, which is the solution to the problem.

```java
class Solution {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        
        // Iterate backwards. For each index i, the total energy of the path
        // starting at i+k has already been computed and stored in energy[i+k].
        for (int i = n - 1; i >= 0; i--) {
            if (i + k < n) {
                energy[i] += energy[i + k];
            }
        }
        
        // The modified energy array now holds the total energy for each starting point.
        // Find the maximum value in this array.
        int maxEnergy = Integer.MIN_VALUE;
        for (int totalEnergy : energy) {
            maxEnergy = Math.max(maxEnergy, totalEnergy);
        }
        
        return maxEnergy;
    }
}
```
### Algorithm
*   Iterate backward through the `energy` array from `i = n-1` down to `0`.
*   For each `i`, if `i + k < n`, update `energy[i]` by adding `energy[i+k]` to it. This works because `energy[i+k]` would have already been updated to hold the total path sum from that point.
*   After the first loop, the `energy` array is transformed such that `energy[i]` holds the total path sum starting at `i`.
*   Iterate through the modified `energy` array to find and return the maximum value.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```