Problem of The Day: Taking Maximum Energy From the Mystic Dungeon

4 min read 902 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        N = len(energy)
        memo = {}
        def dp(i):
            if i >= N:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = dp(i + k) + energy[i]
            return memo[i]

        ans = float('-inf')
        for i in range(N):
            ans = max(ans, dp(i))
        return ans

public class Solution {
    private Dictionary<int, int> Memo = new Dictionary<int,int>();

    private int DP(int i, int[] energy, int k) {
        if (i >= energy.Length) {
            return 0;
        }
        if (Memo.ContainsKey(i)) {
            return Memo[i];
        }
        Memo[i] = DP(i + k, energy, k) + energy[i];
        return Memo[i];
    }

    public int MaximumEnergy(int[] energy, int k) {
        int result = int.MinValue;
        for (int i = 0; i < energy.Length; i ++) {
            result = Math.Max(result, DP(i, energy, k));
        }
        return result;
    }
}

• time: O(n)
• space: O(n)

Bottom-up approach

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        N = len(energy)
        # 1. Create a DP table (same size as energy)
        dp = [0] * N
        
        # 2. Iterate backwards: since i depends on i + k, 
        # we must compute higher indices first.
        for i in range(N - 1, -1, -1):
            if i + k < N:
                # Recursive step: dp[i] = energy[i] + dp[i + k]
                dp[i] = energy[i] + dp[i + k]
            else:
                # Base case: nothing to add beyond the end
                dp[i] = energy[i]
        
        # 3. The answer is the maximum value we calculated
        return max(dp)

Editorial

Approach: Reverse Traversal

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        n = len(energy)
        ans = -inf

        for i in range(n - k, n):
            total = 0
            j = i
            while j >= 0:
                total += energy[j]
                ans = max(ans, total)
                j -= k

        return ans

public class Solution {
    public int MaximumEnergy(int[] energy, int k) {
        int n = energy.Length;
        int ans = int.MinValue;
        for (int i = n - k; i < n; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j -= k) {
                sum += energy[j];
                if (sum > ans)
                    ans = sum;
            }
        }
        return ans;
    }
}

• time: O(n)
• space: O(1)