Taking Maximum Energy From the Mystic Dungeon[M,Array,Prefix Sum]

https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon/description/

In a mystic dungeon, n magicians are standing in a line. Each magician has an attribute that gives you energy. Some magicians can give you negative energy, which means taking energy from you.

You have been cursed in such a way that after absorbing energy from magician i, you will be instantly transported to magician (i + k). This process will be repeated until you reach the magician where (i + k) does not exist.

In other words, you will choose a starting point and then teleport with k jumps until you reach the end of the magicians' sequence, absorbing all the energy during the journey.

You are given an array energy and an integer k. Return the maximum possible energy you can gain.

 

Example 1:

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

Output: 3

Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.

Example 2:

Input: energy = [-2,-3,-1], k = 2

Output: -1

Explanation: We can gain a total energy of -1 by starting from magician 2.

 

Constraints:

• 1 <= energy.length <= 105
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

1. Python

class Solution:

    def helper(self,lst:list,k:int)->int:
        if not lst : return 0
        else : return lst[0]+self.helper(lst[k:],k)

    def maximumEnergy(self, energy: List[int], k: int) -> int:

        e = min(energy)
        for i in range(0,len(energy)):
            e=max(e,self.helper(energy[i:],k))
        return e;

처음에 이렇게 코딩했더니, length가 큰 test case에서 자꾸 시간초과가 떴다.

도저히 time complexity를 줄일 방안이 생각 안 나서 gpt 찬스..

 

진짜 개판치고 있었는데 답안은 간단했다. Dynamic Programming의 힘이란.. 대단하다 진짜

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        for i in range(len(energy) - k - 1 , -1 , -1) : energy[i] += energy[i + k]
        return max(energy)

 

 

2. C

 

int maximumEnergy(int* energy, int energySize, int k) {
    for(int i=energySize-k-1;i>-1;i--){
        energy[i] = energy[i] + energy[i+k];
    }

    int ans= INT_MIN;
    for(int j=0;j<energySize;j++){
        if(ans<energy[j]){
            ans = energy[j];
        }
    }
    return ans;

}

 

DP를 살려서 C코딩을 했다. array 안에서 min, max 구하는 기능이 없어서 INT_MAX/MIN을 가져왔음

근데 생각해보면, 어차피 지금 DP로 싹 갈아엎은 array라 그냥 아무거나 energy[0] 이렇게 해도 되었을듯 하다.

 

3. C++

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        for(int i=energy.size()-k-1;i>-1;i--){
            energy[i] += energy[i+k];
        }
        int ans = *max_element(energy.begin(),energy.end());
        return ans;
    }
};

 

쉽지 않은 DP의 세계이다..