From 24e6d065fa365234f842125c268e75aa17c31388 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 9 Oct 2025 20:45:08 -0600 Subject: 3147. taking maximum energy from the mystic dungeon --- taking_max_energy_mystic_dungeon.c | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 taking_max_energy_mystic_dungeon.c (limited to 'taking_max_energy_mystic_dungeon.c') diff --git a/taking_max_energy_mystic_dungeon.c b/taking_max_energy_mystic_dungeon.c new file mode 100644 index 0000000..1838d1a --- /dev/null +++ b/taking_max_energy_mystic_dungeon.c @@ -0,0 +1,35 @@ +// 3147. Taking Maximum Energy From the Mystic Dungeon +#include "leetcode.h" + +/* + * in a mystic dungeon, 'n' magicians are standing in a line. each magician has + * an attribute that gives you energe. 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 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. note + * that when you are reach a magician, you must take energy from them, whether + * it is positive or negative. + */ + +int maximumEnergy(int *energy, int energySize, int k) { + int *dp = (int *)malloc(energySize * sizeof(int)); + int ans = INT_MIN; + for (int i = energySize - 1; i >= 0; --i) { + int next = (i + k < energySize) ? dp[i + k] : 0; + dp[i] = energy[i] + next; + if (dp[i] > ans) + ans = dp[i]; + } + free(dp); + return ans; +} + +int main() { + int e1[] = {5, 2, -10, -5, -1}, e2[] = {-2, -3, -1}; + printf("%d\n", maximumEnergy(e1, ARRAY_SIZE(e1), 3)); // expect: 3 + printf("%d\n", maximumEnergy(e2, ARRAY_SIZE(e2), 2)); // expect: -1 +} -- cgit v1.2.3