We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Taking Maximum Energy From the Mystic Dungeon

Number: 3383

Difficulty: Medium

Paid? No

Companies: IBM

Problem Description

Given an array energy and an integer k, determine the maximum energy you can collect by choosing a starting magician and then repeatedly “jumping” k steps. At each visited magician you collect their energy (which can be negative as well). You must continue this process until the next jump would take you out of bounds. The task is to choose the starting point such that the sum of energies collected by repeatedly jumping by k is maximized.

Key Insights

  • The energy collected from a starting index i consists of energy[i] plus the results from starting at i+k.
  • A dynamic programming (DP) approach can be used by iterating backwards: dp[i] = energy[i] + (dp[i+k] if i+k is within bounds).
  • The maximum answer is the maximum value across all computed dp[i] values.
  • This reverse iteration avoids redundant recomputation and ensures an O(n) solution.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the energy array. Space Complexity: O(n) for the DP array.

Solution

The solution uses a dynamic programming approach by iterating backwards from the last magician to the first. For each position i, we calculate the maximum energy you can gather if you start from that position by taking energy[i] and adding the maximum energy from the position i+k (if valid). This avoids recomputation by storing results for positions that have already been computed. The maximum value among all starting positions is the answer.

Code Solutions

# Python solution using dynamic programming
def max_energy(energy, k):
    n = len(energy)
    # Initialize a DP array of length n with default values 0
    dp = [0] * n
    
    # Traverse the energy array in reverse order
    for i in range(n - 1, -1, -1):
        # Base case: start with current energy value
        dp[i] = energy[i]
        # If a jump from the current magician is possible, add that energy
        if i + k < n:
            dp[i] += dp[i + k]
    
    # The answer is the maximum energy that can be obtained from any starting index
    return max(dp)

# Example usage:
print(max_energy([5, 2, -10, -5, 1], 3))  # Output: 3
print(max_energy([-2, -3, -1], 2))         # Output: -1
← Back to All Questions