Editorial
Solution walkthrough
Review the explanation, then compare the reference implementation.
Video explanation
Solution
Intuition
Jumps of exactly k split the dungeon into independent chains of indices with the same remainder modulo k. You may start anywhere in a chain, but once started you must continue to its end. This is a maximum-suffix-sum problem on each chain.
Approach
Process indices from k onward, overwriting energy[i] with the best sum of a chain segment ending there. Either start at i, taking its original energy alone, or extend the best segment ending at i - k. Store the larger of those two values.
Only segments ending in the last k positions represent complete journeys, because precisely those positions have no next jump inside the array. Return the maximum updated value among them. Do not compare all intermediate states: a seemingly good intermediate total may still be forced to collect negative energy later. Starting with actual energy values rather than zero also handles all-negative inputs correctly.
class Solution:
def maximumEnergy(self, energy: List[int], k: int) -> int:
for i in range(k, len(energy)): energy[i] = max(energy[i], energy[i] + energy[i - k])
return max(energy[-k:])Complexity analysis
Let n = energy.length. Time: O(n). Auxiliary space: O(k) because both implementations allocate energy[-k:] / energy.slice(-k) before taking the final maximum, even though the DP updates the input in place.