Taking Maximum Energy From the Mystic Dungeon

Problem

From a coding assessment (2026-10-13), where it was called “Max points with jumps of k”. Same problem as LeetCode #3147 Taking Maximum Energy From the Mystic Dungeon.

A board of spaces, each worth positive or negative points. Start on any space and jump exactly k spaces to the right each time, collecting every space you land on. The game ends when you jump past the last space. Return the maximum total.

Example 1

Input:  game_val = [2, -3, 4, 6, 1], k = 2
Output: 7            # land on 2, 4, 1 (start at index 0)

Example 2 (LeetCode #3147)

Input:  energy = [5, 2, -10, -5, 1], k = 3
Output: 3            # start at index 1: 2 + 1

Constraints

• 1 <= n <= 10^6
• -10^3 <= game_val[i] <= 10^3
• 1 <= k <= n

Thinking

• Brute force idea: try every start and walk i, i+k, i+2k, … to the end: $O(n^2 / k)$, which is $O(n^2)$ for k = 1. Too slow at $n = 10^6$.
• Key insight: once you pick a start the path is fixed; the only choice is the start. Paths share tails: the path from 0 is 0, 2, 4 and the path from 2 is 2, 4. So $dp[i] = \text{val}[i] + dp[i + k] \quad (dp[i] = \text{val}[i] \text{ if } i + k \ge n)$ Fill right to left so dp[i + k] is ready, and return max(dp). That is a suffix sum along each chain r, r+k, r+2k, ….
• Why starting later can win: every landing is mandatory, so you can’t skip a negative in the middle of a path; starting later drops a bad prefix. You can never drop a bad suffix.
• Edge cases to remember: all negative (best is the single best value among spaces that end a chain, i.e. the last k spaces), k = 1 (best suffix sum), k = n (no jumps: max element), n = 1.

Solution

Approach A — my version: DP right to left ✅ best practice

Complexity: Time $O(n)$ · Space $O(n)$ for the copy. dp = game_val[:] makes a copy (dp = game_val would alias the same list and change the caller’s input) and also starts every dp[i] at game_val[i], which is already correct for the last k spaces.

def max_points(game_val: list[int], k: int) -> int:
    n = len(game_val)
    dp = game_val[:]  # dp[i] = total points if you start at i
    for i in range(n - 1, -1, -1):
        if i + k < n:
            dp[i] += dp[i + k]
    return max(dp)

Approach B — brute force: simulate every start

Complexity: Time $O(n^2 / k)$ · Space $O(1)$. sum(game_val[i::k]) is exactly the path from i. Recomputes every shared tail.

def max_points_brute(game_val: list[int], k: int) -> int:
    return max(sum(game_val[i::k]) for i in range(len(game_val)))

Approach C — same DP, in place, starting at n - k - 1

Complexity: Time $O(n)$ · Space $O(1)$ extra, but it overwrites the input. Spaces n-k … n-1 need no update, so start the loop at n - k - 1 and drop the if. Only do this when the caller doesn’t need game_val afterwards (or in an interview, say so).

def max_points_inplace(game_val: list[int], k: int) -> int:
    for i in range(len(game_val) - k - 1, -1, -1):
        game_val[i] += game_val[i + k]       # mutates the input
    return max(game_val)

Approach D — suffix sums per chain with accumulate (Pythonic)

Complexity: Time $O(n)$ · Space $O(n / k)$ per chain. The board splits into k independent chains game_val[r::k]. The answer for a chain is its best suffix sum: reverse it and take the best running sum. Slicing and accumulate run in C.

from itertools import accumulate

def max_points_chains(game_val: list[int], k: int) -> int:
    return max(max(accumulate(reversed(game_val[r::k]))) for r in range(k))

Scratch / Experiments

Max size $n = 10^6$ with k = 1 (one long chain) and k = 1000 (many short chains). The brute force is $O(n^2/k)$, so it only runs at $n = 5000$, k = 1. Approach C mutates, so its timing includes making a copy (fair: you’d copy too if you needed the input later).

Typical results:

All but B are $O(n)$. D is several times faster because the slicing, the running sum and the max all happen in C (a bit less so with many short chains, k = 1000); A and C run one Python-level loop iteration per space. C beats A only by skipping the if.

import random

random.seed(0)
tiny = [random.randint(-1000, 1000) for _ in range(5000)]
big = [random.randint(-1000, 1000) for _ in range(1_000_000)]

def run(fn, vals, k):
    return fn(list(vals), k) if fn is max_points_inplace else fn(vals, k)

for label, vals, k, fns in [
    ("n=5000 k=1   ", tiny, 1, APPROACHES),
    ("n=1e6  k=1   ", big, 1, [f for f in APPROACHES if f is not max_points_brute]),
    ("n=1e6  k=1000", big, 1000, [f for f in APPROACHES if f is not max_points_brute]),
]:
    for fn in fns:
        print(f"{label} {fn.__name__:20s}", end=" ")
        %timeit run(fn, vals, k)

Takeaways

• Pattern: “the path from i is fixed and continues from a later index” → DP from the right: dp[i] = val[i] + dp[next(i)], answer = best dp[i]. With a fixed jump k the board splits into k independent chains, and the DP is just a suffix sum on each chain. Mandatory landings mean you can only trim the start, never the middle.
• Mistakes to avoid:
  • dp = game_val aliases the input; [:], list(...) or .copy() make a real copy.
  • Re-walking the path from every start ($O(n^2/k)$) instead of reusing the shared tail.
  • Off-by-one between 1-based problem pictures (“start at index 1”) and 0-based Python.
  • Initialising the answer to 0: with all-negative values you still have to play, so the answer can be negative.
• Related problems: Jump Game VI (#1696, jump up to k → DP + monotonic deque), Maximum Subarray (#53, same “drop a bad prefix” idea, Kadane), House Robber (#198, DP over a line), Min Cost Climbing Stairs (#746, DP from fixed jumps).