Taking Maximum Energy From the Mystic Dungeon

Taking Maximum Energy From the Mystic Dungeon - 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 reach a magician, you must take energy from them, whether it is negative or positive energy.

Input & Output

Example 1 — Basic Case

$ Input: energy = [5,2,-3,1,-4], k = 2

› Output: 3

💡 Note: Starting from position 1: visit positions 1→3, collecting energy 2+1 = 3. This is better than starting from position 0 (5+(-3)+(-4) = -2) or position 2 ((-3)+(-4) = -7).

Example 2 — All Negative

$ Input: energy = [-2,-3,-1], k = 2

› Output: -1

💡 Note: Starting from position 2: only visit position 2, collecting energy -1. Starting from position 0: visit 0→2, collecting -2+(-1) = -3. Starting from position 1: only visit position 1, collecting -3.

Example 3 — Large Jump

$ Input: energy = [1,2,3,4,5], k = 10

› Output: 5

💡 Note: Since k=10 is larger than the array length, we can only visit one position. The maximum energy is 5 from position 4.

Constraints

1 ≤ energy.length ≤ 10⁴
1 ≤ k ≤ energy.length
-1000 ≤ energy[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of energy values and jump distance k

Process

Try different starting positions, jumping k steps each time

Output

Maximum energy possible from any valid path

Key Takeaway

🎯 Key Insight: Each starting position creates a unique sequence with k-step jumps - find the sequence that maximizes total energy

Asked in

a Amazon 35 M Microsoft 28

The key insight is recognizing that positions can be grouped by their remainder when divided by k, since we always jump exactly k steps. The optimal approach tries each possible starting position within the first k positions and calculates the total energy for that sequence. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Pattern Recognition	O(n)	O(k)	Group positions by remainder when divided by k, then find best path in each group
Brute Force	O(n²)	O(1)	Try every possible starting position and calculate total energy

Optimized with Pattern Recognition — Algorithm Steps

Group positions by remainder when divided by k
For each group, calculate cumulative energy for all possible paths
Return maximum energy among all groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Positions

Positions are grouped by remainder: 0%k, 1%k, 2%k, etc.

Calculate Paths

Each group forms independent sequences

Find Maximum

Return the best path among all groups

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* energy, int energySize, int k) {
    int maxEnergy = INT_MIN;
    
    // Try each possible remainder group (0 to k-1)
    for (int start = 0; start < min(k, energySize); start++) {
        int currentEnergy = 0;
        int pos = start;
        
        // Calculate energy for this sequence
        while (pos < energySize) {
            currentEnergy += energy[pos];
            pos += k;
        }
        
        if (currentEnergy > maxEnergy) {
            maxEnergy = currentEnergy;
        }
    }
    
    return maxEnergy;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int energy[100];
    int energySize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        energy[energySize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(energy, energySize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

We visit each position exactly once while grouping and calculating

✓ Linear Growth

Space Complexity

O(k)

We store intermediate results for each of the k groups

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler