Taking Maximum Energy From the Mystic Dungeon

medium dynamic programming suffix sum array

Problem

n magicians stand in a line, each with an energy value in energy[i] (possibly negative). After absorbing energy at magician i you are teleported to magician i + k, and you keep going until i + k no longer exists. You pick a starting magician and must absorb every energy along that chain. Return the maximum total energy you can gain over all starting points.

Inputenergy = [5, 2, -10, -5, 1], k = 3

Output3

Starting at index 1 absorbs energy[1] + energy[4] = 2 + 1 = 3, the best of all chains.

energy (comma-separated)

def maximumEnergy(energy, k):
    n = len(energy)
    dp = energy[:]              # dp[i] = energy gained starting at i
    best = -10**9
    # fill from the back so dp[i + k] is already complete
    for i in range(n - 1, -1, -1):
        if i + k < n:
            dp[i] += dp[i + k]  # chain on the next teleport
        if dp[i] > best:
            best = dp[i]
    return best

function maximumEnergy(energy, k) {
  const n = energy.length;
  const dp = energy.slice();          // dp[i] = energy gained starting at i
  let best = -Infinity;
  // fill from the back so dp[i + k] is already complete
  for (let i = n - 1; i >= 0; i--) {
    if (i + k < n) {
      dp[i] += dp[i + k];             // chain on the next teleport
    }
    if (dp[i] > best) best = dp[i];
  }
  return best;
}

int maximumEnergy(int[] energy, int k) {
    int n = energy.length;
    int[] dp = energy.clone();          // dp[i] = energy gained starting at i
    int best = Integer.MIN_VALUE;
    // fill from the back so dp[i + k] is already complete
    for (int i = n - 1; i >= 0; i--) {
        if (i + k < n) {
            dp[i] += dp[i + k];         // chain on the next teleport
        }
        if (dp[i] > best) best = dp[i];
    }
    return best;
}

int maximumEnergy(vector<int>& energy, int k) {
    int n = energy.size();
    vector<int> dp = energy;             // dp[i] = energy gained starting at i
    int best = INT_MIN;
    // fill from the back so dp[i + k] is already complete
    for (int i = n - 1; i >= 0; i--) {
        if (i + k < n) {
            dp[i] += dp[i + k];         // chain on the next teleport
        }
        if (dp[i] > best) best = dp[i];
    }
    return best;
}

Explanation

From a starting magician i you visit i, i+k, i+2k, … until you run off the end, absorbing every value. The total for a chain that starts at i is exactly energy[i] plus the total of the chain that starts at i + k — so the chains overlap and we can reuse work with dynamic programming.

Define dp[i] = energy gained if you start at index i. The recurrence is dp[i] = energy[i] + dp[i + k] when i + k is still in range, otherwise dp[i] = energy[i] (the chain ends there).

Because dp[i] depends on dp[i + k], we fill the table from the back to the front. By the time we reach i, the value dp[i + k] is already finished, so each cell is computed in O(1). Indices form k independent chains (one per remainder of i mod k), and this single right-to-left pass extends all of them at once.

The answer is the maximum over all starting points max(dp), since the problem lets us choose where to begin. We seed best with a very small number so negative-only inputs (every magician drains you) still return the least-bad chain, as in energy = [-2,-3,-1], k = 2 → -1.

One right-to-left sweep touches every index once, giving linear time and linear extra space (which can be dropped to O(1) by writing the sums back into energy in place).

Time: O(n) Space: O(n)