Skip to content

3147. Taking Maximum Energy From the Mystic Dungeon 👍

  • Time: $O(n)$
  • Space: $O(n)$
1
2
3
4
5
6
7
8
9
class Solution {
 public:
  int maximumEnergy(vector<int>& energy, int k) {
    vector<int> dp(energy);
    for (int i = energy.size() - 1 - k; i >= 0; --i)
      dp[i] += dp[i + k];
    return ranges::max(dp);
  }
};

1
2
3
4
5
6
7
8
class Solution {
  public int maximumEnergy(int[] energy, int k) {
    int[] dp = energy.clone();
    for (int i = energy.length - 1 - k; i >= 0; --i)
      dp[i] += dp[i + k];
    return Arrays.stream(dp).max().getAsInt();
  }
}

1
2
3
4
5
6
7
class Solution:
  def maximumEnergy(self, energy: list[int], k: int) -> int:
    # dp[i] := the sum of energy starting at i
    dp = energy.copy()
    for i in range(len(energy) - 1 - k, -1, -1):
      dp[i] += dp[i + k]
    return max(dp)