題目連結(https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon/description/?envType=daily-question&envId=2025-10-10)

在一個神秘的地牢裡，有 n 位魔法師排成一列。每位魔法師都擁有某種能量，當你接觸到他們時，你會強制吸收該魔法師的能量。能量有可能是正值（表示獲得能量），也可能是負值（表示損失能量）。

你被詛咒了，當你吸收完第 i 位魔法師的能量後，你會立刻被傳送到第 i + k 位魔法師，接著重複這個過程：每次吸收完一位魔法師的能量後都跳到 i + k 的位置。

你可以從任意一位魔法師開始，但傳送的規則固定（每次加 k 的位置跳躍）。

請你回傳你能夠獲得的最大總能量。

DP, prefix sum, 固定步長的題目
想說要放雙十連假，先寫好了結果忘記發ＱＱ就中斷了實慘嗚嗚
剛剛才發現還能發文，就乾脆把三十天發完吧！

1. Repeat（題目重複確認）

• 輸入：陣列 energy ，整數 k(跳躍間隔）
• 輸出：從陣列中按照跳躍規則吸取魔法師能量下能得的最大總能量
• 前提：
  • 1 <= energy.length <= 105
  • 1000 <= energy[i] <= 1000
  • 1 <= k <= energy.length - 1

2. Examples（舉例確認理解）

1. 從某個起點 i 開始，每次跳 k 步：i → i+k → i+2k → ...
2. 收集路徑上所有能量（包括負能量）
3. 找出所有可能起點中，能獲得的最大總能量

Input: energy = [5,2,-10,-5,1], k = 3
Output: 3
Explanation: from magician 1＋4 absorbing 2 + 1 = 3.

3. Approach（解題思路）

方法 1：DP(空間優化版)

• DP思路
  • 每個位置只能被一條路徑經過（因為只能從 i-k 跳到 i）
  • 從後往前計算更簡單：dp[i] = energy[i] + dp[i+k]
  • 只需考慮最後 k 個位置作為可能的終點
• 不需要建新的陣列dp
  • 直接更新原本的陣列 energy，在尚未抵達終點前（終止條件：i + k < n），更新以 i 為起點所得的能量值
  • if(i + k < n) energy[i] += energy[i+k];
• 時間複雜度：O(n)
• 空間複雜度：O(1)

方法 2：只考慮 k 個終點

• 後 k 個位置開始往前累加到不超過序列起點，比較這 k 種可能
• 時間複雜度：O(n)
• 空間複雜度：O(1)

4. Code（C++）

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        int maxsum = INT_MIN;
        // 從後往前遍歷，直接修改原陣列
        for (int i = n - 1; i >= 0 ; i--) {
		        // 跳 k 步還能跳到下一個位置
            if(i + k < n){
                energy[i] += energy[i+k];
            }
            maxsum = max(maxsum, energy[i]);
        }
        return maxsum;
    }
};

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        int maxsum = INT_MIN;
        
        // 只需要從後 k 個位置開始往前累加
        for (int start = n - k; start < n; start++) {
            int sum = 0;
            // 從 start 往前跳，每次跳 k 步
            for(int i = start; i >= 0; i -= k){
                sum += energy[i];
                 maxsum = max(maxsum, sum);
            }
        }
        return maxsum;
    }
};

5. Test 範例

Example : energy = [5,2,-10,-5,1], k = 3

i=4: dp[4] = 1              (終點)
i=3: dp[3] = -5             (終點)
i=2: dp[2] = -10            (終點)
i=1: dp[1] = 2 + dp[4] = 3  ✓ 最大值
i=0: dp[0] = 5 + dp[3] = 0

6. 相關題目與延伸概念

643. Maximum Average Subarray I

1262. Greatest Sum Divisible by Three

2946. Matrix Similarity After Cyclic Shifts

7. 補充：語法＆注意事項

prefix Sum vs. DP(跳躍式總和（Gap Sum))

prefix Sum（前綴和）是資料結構中常見技巧，用來快速查詢區間和。

• 給定一個陣列 A，預先計算一個 prefix 陣列，使得：

prefix[0] = 0
prefix[i+1] = prefix[i] + A[i]

查詢 A[l] + A[l+1] + ... + A[r] 時，可以用：

sum = prefix[r+1] - prefix[l]

這題的步長是固定跳躍間隔 k，並不是查詢「連續」的區間和，所以：

• 雖然也在累加子陣列元素，但它是間隔跳取（i, i+k, i+2k...）
• Prefix Sum 無法快速處理「非連續」跳躍子陣列，改用「跳躍前綴和」

vector<int> dp(n);
for (int i = n - 1; i >= 0; i--) {
    dp[i] = energy[i];
    if (i + k < n) {
        dp[i] += dp[i + k];
    }
    result = max(result, dp[i]);
}

ps. 部分內容經 AI 協助整理