3186. Maximum Total Damage With Spell Casting LeetCode Solution
In this guide, you will get 3186. Maximum Total Damage With Spell Casting LeetCode Solution with the best time and space complexity. The solution to Maximum Total Damage With Spell Casting problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Total Damage With Spell Casting
A magician has various spells.
You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.
It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] – 2, power[i] – 1, power[i] + 1, or power[i] + 2.
Each spell can be cast only once.
Return the maximum possible total damage that a magician can cast.
Example 1:
Input: power = [1,1,3,4]
Output: 6
Explanation:
The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.
Example 2:
Input: power = [7,1,6,6]
Output: 13
Explanation:
The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.
3186. Maximum Total Damage With Spell Casting LeetCode Solution in C++
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
unordered_map<int, int> count;
for (const int damage : power)
++count[damage];
const vector<int> uniqueDamages = getSortedUniqueDamages(count);
const int n = uniqueDamages.size();
// dp[i][k] := the maximum damage using uniqueDamages[0..i], where k
// indicates if the i-th damage is used
vector<vector<long>> dp(n, vector<long>(2));
for (int i = 0; i < n; ++i) {
const long damage = uniqueDamages[i];
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = damage * count[damage];
continue;
}
dp[i][0] = ranges::max(dp[i - 1]);
dp[i][1] = damage * count[damage];
if (i >= 1 && uniqueDamages[i - 1] != damage - 1 &&
uniqueDamages[i - 1] != damage - 2) {
dp[i][1] += max(dp[i - 1][0], dp[i - 1][1]);
} else if (i >= 2 && uniqueDamages[i - 2] != damage - 2) {
dp[i][1] += max(dp[i - 2][0], dp[i - 2][1]);
} else if (i >= 3) {
dp[i][1] += max(dp[i - 3][0], dp[i - 3][1]);
}
}
return ranges::max(dp.back());
}
private:
vector<int> getSortedUniqueDamages(const unordered_map<int, int>& count) {
vector<int> uniqueDamages;
for (const auto& [damage, _] : count)
uniqueDamages.push_back(damage);
ranges::sort(uniqueDamages);
return uniqueDamages;
}
}; /* code provided by PROGIEZ */
3186. Maximum Total Damage With Spell Casting LeetCode Solution in Java
class Solution {
public long maximumTotalDamage(int[] power) {
Map<Integer, Integer> count = new HashMap<>();
for (final int damage : power)
count.merge(damage, 1, Integer::sum);
List<Integer> uniqueDamages = getSortedUniqueDamages(count);
final int n = uniqueDamages.size();
// dp[i][k] := the maximum damage using uniqueDamages[0..i], where k
// indicates if the i-th damage is used
long[][] dp = new long[n][2];
for (int i = 0; i < n; ++i) {
final int damage = uniqueDamages.get(i);
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = (long) damage * count.get(damage);
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = (long) damage * count.get(damage);
if (i >= 1 && uniqueDamages.get(i - 1) != damage - 1 &&
uniqueDamages.get(i - 1) != damage - 2) {
dp[i][1] += Math.max(dp[i - 1][0], dp[i - 1][1]);
} else if (i >= 2 && uniqueDamages.get(i - 2) != damage - 2) {
dp[i][1] += Math.max(dp[i - 2][0], dp[i - 2][1]);
} else if (i >= 3) {
dp[i][1] += Math.max(dp[i - 3][0], dp[i - 3][1]);
}
}
return Math.max(dp[n - 1][0], dp[n - 1][1]);
}
private List<Integer> getSortedUniqueDamages(Map<Integer, Integer> count) {
List<Integer> uniqueDamages = new ArrayList<>(count.keySet());
Collections.sort(uniqueDamages);
return uniqueDamages;
}
} // code provided by PROGIEZ
3186. Maximum Total Damage With Spell Casting LeetCode Solution in Python
class Solution:
def maximumTotalDamage(self, power: list[int]) -> int:
count = collections.Counter(power)
uniqueDamages = sorted(count.keys())
# dp[i][k] := the maximum damage using uniqueDamages[0..i], where k
# indicates if the i-th damage is used
dp = [[0] * 2 for _ in range(len(uniqueDamages))]
for i, damage in enumerate(uniqueDamages):
if i == 0:
dp[0] = [0, damage * count[damage]]
continue
dp[i][0] = max(dp[i - 1])
dp[i][1] = damage * count[damage]
if i >= 1 and uniqueDamages[i - 1] not in (damage - 1, damage - 2):
dp[i][1] += max(dp[i - 1])
elif i >= 2 and uniqueDamages[i - 2] != damage - 2:
dp[i][1] += max(dp[i - 2])
elif i >= 3:
dp[i][1] += max(dp[i - 3])
return max(dp[-1]) # code by PROGIEZ
