Taking maximum energy from the mystic dungeon

Array Prefix Sum

61.0% acceptance

Feb 24, 2026

587

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). You will choose a starting point and then teleport with k jumps until you reach the end. You are given an array energy and an integer k. Return the maximum possible energy you can gain.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_energy(energy: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let n = energy.len();
    // dp[i] = max energy starting from position i (sum from i to end of chain)
    let mut dp = energy.clone();
    for i in (0..n - k).rev() {
      dp[i] = energy[i] + dp[i + k];
    }
    *dp.iter().max().unwrap()
  }
}