LeetCode Daily Problem P3147 Maximum Energy Drawn from a Mage

---

Timeline

Timeline

2025-10-10

init

Array, Dynamic Programming

---

Problem:

P3147 Maximum Energy Drawn from a Mage

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, and there are paths {0…k-1} - {n-1-k…n-1}
The starting point of each path is 0~k-1. Calculate the maximum energy starting from a certain starting point for each path, then find the maximum among the maximum energies of these paths.
For a path, the maximum energy is the maximum sum from a starting point to the last value. So we might as well traverse from the last starting point backward, recording 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, dynamic programming can also be used to solve it:
Suppose dp[i] is the maximum energy obtained when reaching the i-th mage, 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 we eventually reach an area without mages, we must reach the last k mages. 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;
  }
};