Skip to content

← leetcode

Taking Maximum Energy From the Mystic Dungeon

· Medium

LeetCode problem 3147

Simply treat the original energy vector as a dp array, where the recursive equation is:

dp[i] = dp[i+k] + energy[i]

Thus, we can simply iterate through energy in reverse, checking if index i+k exists before adding it to energy[i] and greedily selecting the largest value as our ans.

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

code

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        int ans = INT32_MIN;

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

        return ans;
    }
};

complexity

  • Time: O(n) where n denotes the number of elements inside energy
  • Space: O(1)

time taken

  • 5 minutes and 9 seconds