LeetCode Daily Problem P3147 Maximum Energy Drawn from the Magician

---

Timeline

timeline

2025-10-10

init

array, dynamic programming

---

Problem:

P3147 Maximum Energy Drawn from the Magician

https://leetcode.cn/problems/taking-maximum-energy-from-the-mystic-dungeon/?envType=daily-question&envId=2025-10-10

traverse from back to front

Assume we need to start from 0…k-1, there are paths {0…k-1} - {n-1-k…n-1}
Each path starts from 0~k-1, calculate the maximum energy starting from a certain starting point for each path, then find the maximum among these paths.
For a path, the maximum energy is to find the maximum sum from a starting point to the last value, so we might as well traverse from the last starting point forward and record the maximum sum.

#include <algorithm>
#include <climits>
#include <vector>
using std::vector;

class Solution {
public:
  int maximumEnergy(vector<int> &energy, int k) {

    int i, j;
    int total = 0;
    int n = energy.size();
    vector<int> way(n, INT_MIN);

    for (i = 0; i < k; i++) { // each path
      j = 0;
      while (i + j * k < n) {
        j++;
      }
      j--;
      total = 0;

      while (j >= 0) {
        total += energy[i + j * k];
        way[i] = std::max(way[i], total);
        j--;
      }
    }

    return *std::max_element(way.begin(), way.end());
  }
};

#include <stdio.h>
int main() {
  Solution s;
  vector<int> vec = {5, 2, -10, -5, 1};
  printf("%d\n", s.maximumEnergy(vec, 3));
}

dynamic programming

Because the maximum energy is related to previous states, we can also use dynamic programming to solve it:
Suppose dp[i] is the maximum energy obtained when reaching the i-th magician, then

$$\text dp[i] = \text max(energy[i] \space,\space dp[i-k] + \text energy[i])$$

Boundary conditions:

$$\text dp[i] = energy[i] \space \text(i<k)$$

Since the final area has no magicians, we must reach the last k magicians. Therefore, the final maximum is found from the last k dp values.

#include <algorithm>
#include <vector>
using std::vector;

class Solution {
public:
  int maximumEnergy(vector<int> &energy, int k){

    int n = energy.size();
    int res;
    vector<int> dp(n);

    std::copy(energy.begin(), energy.end(), dp.begin());

    for (int i = k; i < n; i++) {
      dp[i] = std::max(energy[i], dp[i - k] + energy[i]);
    }

    res = *std::max_element(dp.end() - k, dp.end());

    return res;
  }
};