3147: Taking-Maximum-Energy-From-the-Mystic-Dungeon
Medium

table of contents

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 taken