# Taking Maximum Energy From the Mystic Dungeon

[link](https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon/) · Medium · `array`, `dynamic programming`, `prefix sum`

> "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.

## 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.

```python
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.

```python
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).

```python
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.

```python
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:

| Approach | $n=5000$, $k=1$ | $n=10^6$, $k=1$ | $n=10^6$, $k=1000$ |
|---|---|---|---|
| A DP ✅ | ~0.34 ms | ~80 ms | ~80 ms |
| B brute force | ~54 ms | (hours) | (seconds–minutes) |
| C in place (+copy) | ~0.26 ms | ~65 ms | ~62 ms |
| D `accumulate` chains | ~0.08 ms | ~20 ms | ~35 ms |

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`.

```python
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).

---

From https://taosu.blog/notes/3147-taking-maximum-energy-from-the-mystic-dungeon