Taking Maximum Energy From the Mystic Dungeon

main.md

Question

Approach

I notice the teleport pattern partitions indices into k independent chains: indices r, r+k, r+2k, ... for each residue r = 0..k-1. Starting at any index means picking a suffix of one of those chains and summing all elements in that suffix. So for each chain I compute the maximum suffix sum (scanning its elements from the end toward the front), and the answer is the maximum among those k values.

Implementation

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        n = len(energy)
        best = -10**18 

        for r in range(k):
            last = r + ((n - 1 - r) // k) * k
            cur = 0
            best_r = -10**18
            i = last
            while i >= r:
                cur += energy[i]   
                if cur > best_r:
                    best_r = cur
                i -= k
            if best_r > best:
                best = best_r

        return best

Complexities

• Time: O(n)
• Space: O(1)