{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "18de98838bfd",
   "metadata": {},
   "source": [
    "# Taking Maximum Energy From the Mystic Dungeon\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon/)  |\n",
    "| Difficulty | Medium                    |\n",
    "| Topics     | `array`, `dynamic programming`, `prefix sum`                     |\n",
    "| Date       | 2026-10-13                              |\n",
    "| Status     | Solved                                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f62d0c5b0080",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> *From a coding assessment (2026-10-13), where it was called \"Max points with jumps of k\". Same\n",
    "> problem as LeetCode #3147 Taking Maximum Energy From the Mystic Dungeon.*\n",
    ">\n",
    "> A board of spaces, each worth positive or negative points. Start on any space and jump exactly\n",
    "> `k` spaces to the right each time, collecting every space you land on. The game ends when you\n",
    "> jump past the last space. Return the maximum total.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  game_val = [2, -3, 4, 6, 1], k = 2\n",
    "Output: 7            # land on 2, 4, 1 (start at index 0)\n",
    "```\n",
    "\n",
    "**Example 2** (LeetCode #3147)\n",
    "```\n",
    "Input:  energy = [5, 2, -10, -5, 1], k = 3\n",
    "Output: 3            # start at index 1: 2 + 1\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `1 <= n <= 10^6`\n",
    "- `-10^3 <= game_val[i] <= 10^3`\n",
    "- `1 <= k <= n`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cdbe4e734fa",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** try every start and walk `i, i+k, i+2k, …` to the end: $O(n^2 / k)$,\n",
    "  which is $O(n^2)$ for `k = 1`. Too slow at $n = 10^6$.\n",
    "- **Key insight:** once you pick a start the path is fixed; the only choice is the start. Paths\n",
    "  **share tails**: the path from 0 is `0, 2, 4` and the path from 2 is `2, 4`. So\n",
    "  $$dp[i] = \\text{val}[i] + dp[i + k] \\quad (dp[i] = \\text{val}[i] \\text{ if } i + k \\ge n)$$\n",
    "  Fill right to left so `dp[i + k]` is ready, and return `max(dp)`. That is a **suffix sum along\n",
    "  each chain** `r, r+k, r+2k, …`.\n",
    "- **Why starting later can win:** every landing is mandatory, so you can't skip a negative in the\n",
    "  middle of a path; starting later drops a bad prefix. You can never drop a bad *suffix*.\n",
    "- **Edge cases to remember:** all negative (best is the single best value among spaces that end\n",
    "  a chain, i.e. the last `k` spaces), `k = 1` (best suffix sum), `k = n` (no jumps: max element),\n",
    "  `n = 1`."
   ]
  },
  {
   "cell_type": "code",
   "id": "9ec5047b776d",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Setup: run this cell first. Lets you run pytest tests inside the notebook.\n",
    "try:\n",
    "    import ipytest\n",
    "except ImportError:  # Colab and other fresh kernels don't ship ipytest\n",
    "    %pip install -q ipytest\n",
    "    import ipytest\n",
    "import pytest\n",
    "\n",
    "ipytest.autoconfig()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37c4d1c7808d",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my version: DP right to left ✅ best practice\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(n)$ for the copy.\n",
    "`dp = game_val[:]` makes a **copy** (`dp = game_val` would alias the same list and change the\n",
    "caller's input) and also starts every `dp[i]` at `game_val[i]`, which is already correct for the\n",
    "last `k` spaces."
   ]
  },
  {
   "cell_type": "code",
   "id": "b77258c4d947",
   "metadata": {},
   "source": [
    "def max_points(game_val: list[int], k: int) -> int:\n",
    "    n = len(game_val)\n",
    "    dp = game_val[:]  # dp[i] = total points if you start at i\n",
    "    for i in range(n - 1, -1, -1):\n",
    "        if i + k < n:\n",
    "            dp[i] += dp[i + k]\n",
    "    return max(dp)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "2e99aec30406",
   "metadata": {},
   "source": [
    "### Approach B — brute force: simulate every start\n",
    "\n",
    "**Complexity:** Time $O(n^2 / k)$ · Space $O(1)$.\n",
    "`sum(game_val[i::k])` is exactly the path from `i`. Recomputes every shared tail."
   ]
  },
  {
   "cell_type": "code",
   "id": "6474a086e90c",
   "metadata": {},
   "source": [
    "def max_points_brute(game_val: list[int], k: int) -> int:\n",
    "    return max(sum(game_val[i::k]) for i in range(len(game_val)))"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "9000dbd44480",
   "metadata": {},
   "source": [
    "### Approach C — same DP, in place, starting at `n - k - 1`\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(1)$ extra, but **it overwrites the input**.\n",
    "Spaces `n-k … n-1` need no update, so start the loop at `n - k - 1` and drop the `if`. Only do\n",
    "this when the caller doesn't need `game_val` afterwards (or in an interview, say so)."
   ]
  },
  {
   "cell_type": "code",
   "id": "8e78b2fed107",
   "metadata": {},
   "source": [
    "def max_points_inplace(game_val: list[int], k: int) -> int:\n",
    "    for i in range(len(game_val) - k - 1, -1, -1):\n",
    "        game_val[i] += game_val[i + k]       # mutates the input\n",
    "    return max(game_val)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "aba906787e1f",
   "metadata": {},
   "source": [
    "### Approach D — suffix sums per chain with `accumulate` (Pythonic)\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(n / k)$ per chain.\n",
    "The board splits into `k` independent chains `game_val[r::k]`. The answer for a chain is its\n",
    "best suffix sum: reverse it and take the best running sum. Slicing and `accumulate` run in C."
   ]
  },
  {
   "cell_type": "code",
   "id": "4587f7a7a860",
   "metadata": {},
   "source": [
    "from itertools import accumulate\n",
    "\n",
    "def max_points_chains(game_val: list[int], k: int) -> int:\n",
    "    return max(max(accumulate(reversed(game_val[r::k]))) for r in range(k))"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "d142f564fd05",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "Every approach runs against every case. Approach C mutates its input, so every call gets a copy\n",
    "(`list(game_val)`); otherwise later approaches would see a modified board."
   ]
  },
  {
   "cell_type": "code",
   "id": "f5ecdcc5d478",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "APPROACHES = [\n",
    "    max_points,\n",
    "    max_points_brute,\n",
    "    max_points_inplace,\n",
    "    max_points_chains,\n",
    "]\n",
    "\n",
    "CASES = [\n",
    "    ([2, -3, 4, 6, 1], 2, 7),\n",
    "    ([5, 2, -10, -5, 1], 3, 3),               # LeetCode #3147 example 1\n",
    "    ([-2, -3, -1], 2, -1),                    # LeetCode #3147 example 2: all negative\n",
    "    ([7], 1, 7),                              # n = 1\n",
    "    ([-5], 1, -5),                            # n = 1, negative\n",
    "    ([3, -1, 2, 4], 1, 8),                    # k = 1: best suffix sum (whole array)\n",
    "    ([5, -10, 1, 2], 1, 3),                   # k = 1: dropping the prefix wins\n",
    "    ([1, 9, -4, 3], 4, 9),                    # k = n: no jumps, max element\n",
    "    ([10, 0, -20, 0, 1], 2, 1),               # start later to skip a bad prefix\n",
    "    ([-1, -1, -1, 1000], 3, 1000),            # bad prefix vs good last landing\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", APPROACHES)\n",
    "@pytest.mark.parametrize(\"game_val, k, expected\", CASES)\n",
    "def test_max_points(fn, game_val, k, expected):\n",
    "    assert fn(list(game_val), k) == expected  # copy: max_points_inplace mutates"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "f747a4328902",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "Max size $n = 10^6$ with `k = 1` (one long chain) and `k = 1000` (many short chains). The brute\n",
    "force is $O(n^2/k)$, so it only runs at $n = 5000$, `k = 1`. Approach C mutates, so its timing\n",
    "includes making a copy (fair: you'd copy too if you needed the input later).\n",
    "\n",
    "Typical results:\n",
    "\n",
    "| Approach | $n=5000$, $k=1$ | $n=10^6$, $k=1$ | $n=10^6$, $k=1000$ |\n",
    "|---|---|---|---|\n",
    "| A DP ✅ | ~0.34 ms | ~80 ms | ~80 ms |\n",
    "| B brute force | ~54 ms | (hours) | (seconds–minutes) |\n",
    "| C in place (+copy) | ~0.26 ms | ~65 ms | ~62 ms |\n",
    "| D `accumulate` chains | ~0.08 ms | ~20 ms | ~35 ms |\n",
    "\n",
    "All but B are $O(n)$. D is several times faster because the slicing, the running sum and the\n",
    "`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\n",
    "skipping the `if`."
   ]
  },
  {
   "cell_type": "code",
   "id": "aa1d7b59f161",
   "metadata": {},
   "source": [
    "import random\n",
    "\n",
    "random.seed(0)\n",
    "tiny = [random.randint(-1000, 1000) for _ in range(5000)]\n",
    "big = [random.randint(-1000, 1000) for _ in range(1_000_000)]\n",
    "\n",
    "def run(fn, vals, k):\n",
    "    return fn(list(vals), k) if fn is max_points_inplace else fn(vals, k)\n",
    "\n",
    "for label, vals, k, fns in [\n",
    "    (\"n=5000 k=1   \", tiny, 1, APPROACHES),\n",
    "    (\"n=1e6  k=1   \", big, 1, [f for f in APPROACHES if f is not max_points_brute]),\n",
    "    (\"n=1e6  k=1000\", big, 1000, [f for f in APPROACHES if f is not max_points_brute]),\n",
    "]:\n",
    "    for fn in fns:\n",
    "        print(f\"{label} {fn.__name__:20s}\", end=\" \")\n",
    "        %timeit run(fn, vals, k)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "bbe7a0f9140d",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"the path from `i` is fixed and continues from a later index\" → **DP from the\n",
    "  right**: `dp[i] = val[i] + dp[next(i)]`, answer = best `dp[i]`. With a fixed jump `k` the\n",
    "  board splits into `k` independent chains, and the DP is just a **suffix sum on each chain**.\n",
    "  Mandatory landings mean you can only trim the start, never the middle.\n",
    "- **Mistakes to avoid:**\n",
    "  - `dp = game_val` aliases the input; `[:]`, `list(...)` or `.copy()` make a real copy.\n",
    "  - Re-walking the path from every start ($O(n^2/k)$) instead of reusing the shared tail.\n",
    "  - Off-by-one between 1-based problem pictures (\"start at index 1\") and 0-based Python.\n",
    "  - Initialising the answer to `0`: with all-negative values you still have to play, so the\n",
    "    answer can be negative.\n",
    "- **Related problems:** Jump Game VI (#1696, jump *up to* `k` → DP + monotonic deque), Maximum\n",
    "  Subarray (#53, same \"drop a bad prefix\" idea, Kadane), House Robber (#198, DP over a line),\n",
    "  Min Cost Climbing Stairs (#746, DP from fixed jumps)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}