Maximum total damage with spell casting

Array Hash Table Two Pointers Binary Search Dynamic Programming Sorting Counting

45.0% acceptance

Feb 24, 2026

749

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. If a magician decides to cast a spell with damage power[i], they cannot cast any spell with damage 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_total_damage(power: Vec<i32>) -> i64 {
    use std::collections::HashMap;
    let mut freq: HashMap<i32, i64> = HashMap::new();
    for &p in &power {
      *freq.entry(p).or_insert(0) += p as i64;
    }
    let mut vals: Vec<i32> = freq.keys().cloned().collect();
    vals.sort_unstable();
    let m = vals.len();
    let mut dp = vec![0i64; m + 1];
    for i in 0..m {
      let v = vals[i];
      let total_val = freq[&v];
      // Find the latest index j < i where vals[j] < v - 2
      let mut lo = 0usize;
      let mut hi = i;
      while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if vals[mid] < v - 2 {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      }
      // lo is the first index where vals[lo] >= v - 2
      // so last valid index is lo - 1 (or 0 if lo == 0)
      let prev_ok = if lo == 0 { 0 } else { dp[lo] };
      dp[i + 1] = dp[i].max(prev_ok + total_val);
    }
    dp[m]
  }
}