3186. Maximum Total Damage With Spell Casting

Description

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.

Constraints:

1 <= power.length <= 10⁵
1 <= power[i] <= 10⁹

Solutions

Solution 1: Binary Search + Memoization

We can first sort the array $\text{power}$, use a hash table $\text{cnt}$ to record the occurrence count of each damage value, and then iterate through the array $\text{power}$. For each damage value $x$, we can determine the index of the next damage value that can be used when using a spell with damage value $x$, which is the index of the first damage value greater than $x + 2$. We can use binary search to find this index and record it in the array $\text{nxt}$.

Next, we define a function $\text{dfs}$ to calculate the maximum damage value that can be obtained starting from the $i$-th damage value.

In the $\text{dfs}$ function, we can choose to skip the current damage value, so we can skip all the same damage values of the current one and directly jump to $i + \text{cnt}[x]$, obtaining a damage value of $\text{dfs}(i + \text{cnt}[x])$; or we can choose to use the current damage value, so we can use all the same damage values of the current one and then jump to the index of the next damage value, obtaining a damage value of $x \times \text{cnt}[x] + \text{dfs}(\text{nxt}[i])$, where $\text{nxt}[i]$ represents the index of the first damage value greater than $x + 2$. We take the maximum of these two cases as the return value of the function.

To avoid repeated calculations, we can use memoization, storing the results that have already been calculated in an array $\text{f}$. Thus, when calculating $\text{dfs}(i)$, if $\text{f}[i]$ is not $0$, we directly return $\text{f}[i]$.

The answer is $\text{dfs}(0)$.

The time complexity is $O(n \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\text{power}$.

Solution 2: Binary Search + Dynamic Programming

Thinking

Taking damage $x$ forbids every other value in $[x-2,x+2]$, while equal copies of $x$ may all be taken. $n$ can be $10^5$, so subsets of the distinct damages are exponential.

After sorting, skipping the current value always calls a later index first. When the damages are distinct and adjacent, that call advances by $1$, so the chain has length $n$ and overflows the stack.

Later indexes are known if we walk backward. Let $f[i]$ be the best damage from index $i$: skipping lands on $i+\textit{cnt}[x]$, and taking lands on the first value greater than $x+2$, which binary search stores ahead of time.

Sort $\textit{power}$ and record the count of each damage in a hash table $\textit{cnt}$. For every index $i$, binary search stores in $\textit{nxt}[i]$ the first position whose value is greater than $\textit{power}[i] + 2$.

Let $f[i]$ be the maximum damage obtainable from index $i$, with $f[n] = 0$. The answer is $f[0]$.

Fill $i$ from $n - 1$ down to $0$. Write $x = \textit{power}[i]$. Skipping every copy of $x$ yields $f[i + \textit{cnt}[x]]$. Taking those copies yields $x \times \textit{cnt}[x] + f[\textit{nxt}[i]]$. An index past $n$ contributes $0$. Take the larger value:

\[f[i] = \max(f[i + \textit{cnt}[x]],\ x \times \textit{cnt}[x] + f[\textit{nxt}[i]])\]

The time complexity is $O(n \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{power}$.

class Solution {
    private Long[] f;
    private int[] power;
    private Map<Integer, Integer> cnt;
    private int[] nxt;
    private int n;

    public long maximumTotalDamage(int[] power) {
        Arrays.sort(power);
        this.power = power;
        n = power.length;
        f = new Long[n];
        cnt = new HashMap<>(n);
        nxt = new int[n];
        for (int i = 0; i < n; ++i) {
            cnt.merge(power[i], 1, Integer::sum);
            int l = Arrays.binarySearch(power, power[i] + 3);
            l = l < 0 ? -l - 1 : l;
            nxt[i] = l;
        }
        return dfs(0);
    }

    private long dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        long a = dfs(i + cnt.get(power[i]));
        long b = 1L * power[i] * cnt.get(power[i]) + dfs(nxt[i]);
        return f[i] = Math.max(a, b);
    }
}


// Solution 2
class Solution {
    public long maximumTotalDamage(int[] power) {
        Arrays.sort(power);
        int n = power.length;
        Map<Integer, Integer> cnt = new HashMap<>(n);
        int[] nxt = new int[n];
        for (int i = 0; i < n; ++i) {
            cnt.merge(power[i], 1, Integer::sum);
            int l = Arrays.binarySearch(power, power[i] + 3);
            l = l < 0 ? -l - 1 : l;
            nxt[i] = l;
        }
        long[] f = new long[n + 1];
        for (int i = n - 1; i >= 0; --i) {
            int j = i + cnt.get(power[i]);
            long a = j <= n ? f[j] : 0;
            long b = 1L * power[i] * cnt.get(power[i]) + f[nxt[i]];
            f[i] = Math.max(a, b);
        }
        return f[0];
    }
}

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        sort(power.begin(), power.end());
        this->power = power;
        n = power.size();
        f.resize(n);
        nxt.resize(n);
        for (int i = 0; i < n; ++i) {
            cnt[power[i]]++;
            nxt[i] = upper_bound(power.begin() + i + 1, power.end(), power[i] + 2) - power.begin();
        }
        return dfs(0);
    }

private:
    unordered_map<int, int> cnt;
    vector<long long> f;
    vector<int> power;
    vector<int> nxt;
    int n;

    long long dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (f[i]) {
            return f[i];
        }
        long long a = dfs(i + cnt[power[i]]);
        long long b = 1LL * power[i] * cnt[power[i]] + dfs(nxt[i]);
        return f[i] = max(a, b);
    }
};


// Solution 2
class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        sort(power.begin(), power.end());
        int n = power.size();
        unordered_map<int, int> cnt;
        vector<int> nxt(n);
        for (int i = 0; i < n; ++i) {
            cnt[power[i]]++;
            nxt[i] = upper_bound(power.begin() + i + 1, power.end(), power[i] + 2) - power.begin();
        }
        vector<long long> f(n + 1);
        for (int i = n - 1; i >= 0; --i) {
            int j = i + cnt[power[i]];
            long long a = j <= n ? f[j] : 0;
            long long b = 1LL * power[i] * cnt[power[i]] + f[nxt[i]];
            f[i] = max(a, b);
        }
        return f[0];
    }
};

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            a = dfs(i + cnt[power[i]])
            b = power[i] * cnt[power[i]] + dfs(nxt[i])
            return max(a, b)

        n = len(power)
        cnt = Counter(power)
        power.sort()
        nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)]
        return dfs(0)



# Solution 2
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        n = len(power)
        cnt = Counter(power)
        power.sort()
        nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)]
        f = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            j = i + cnt[power[i]]
            a = f[j] if j <= n else 0
            b = power[i] * cnt[power[i]] + f[nxt[i]]
            f[i] = max(a, b)
        return f[0]

func maximumTotalDamage(power []int) int64 {
	n := len(power)
	sort.Ints(power)
	cnt := map[int]int{}
	nxt := make([]int, n)
	f := make([]int64, n)
	for i, x := range power {
		cnt[x]++
		nxt[i] = sort.SearchInts(power, x+3)
	}
	var dfs func(int) int64
	dfs = func(i int) int64 {
		if i >= n {
			return 0
		}
		if f[i] != 0 {
			return f[i]
		}
		a := dfs(i + cnt[power[i]])
		b := int64(power[i]*cnt[power[i]]) + dfs(nxt[i])
		f[i] = max(a, b)
		return f[i]
	}
	return dfs(0)
}


// Solution 2
func maximumTotalDamage(power []int) int64 {
	n := len(power)
	sort.Ints(power)
	cnt := map[int]int{}
	nxt := make([]int, n)
	f := make([]int64, n+1)
	for i, x := range power {
		cnt[x]++
		nxt[i] = sort.SearchInts(power, x+3)
	}
	for i := n - 1; i >= 0; i-- {
		j := i + cnt[power[i]]
		a := int64(0)
		if j <= n {
			a = f[j]
		}
		b := int64(power[i])*int64(cnt[power[i]]) + f[nxt[i]]
		f[i] = max(a, b)
	}
	return f[0]
}

function maximumTotalDamage(power: number[]): number {
    const n = power.length;
    power.sort((a, b) => a - b);
    const f: number[] = Array(n).fill(0);
    const cnt: Record<number, number> = {};
    const nxt: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        cnt[power[i]] = (cnt[power[i]] || 0) + 1;
        let [l, r] = [i + 1, n];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (power[mid] > power[i] + 2) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        nxt[i] = l;
    }
    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i]) {
            return f[i];
        }
        const a = dfs(i + cnt[power[i]]);
        const b = power[i] * cnt[power[i]] + dfs(nxt[i]);
        return (f[i] = Math.max(a, b));
    };
    return dfs(0);
}



// Solution 2
function maximumTotalDamage(power: number[]): number {
    const n = power.length;
    power.sort((a, b) => a - b);
    const cnt: Record<number, number> = {};
    const nxt: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        cnt[power[i]] = (cnt[power[i]] || 0) + 1;
        let [l, r] = [i + 1, n];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (power[mid] > power[i] + 2) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        nxt[i] = l;
    }
    const f: number[] = Array(n + 1).fill(0);
    for (let i = n - 1; i >= 0; --i) {
        const j = i + cnt[power[i]];
        const a = j <= n ? f[j] : 0;
        const b = power[i] * cnt[power[i]] + f[nxt[i]];
        f[i] = Math.max(a, b);
    }
    return f[0];
}

use std::collections::HashMap;

impl Solution {
    pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
        power.sort();
        let n = power.len();
        let mut cnt = HashMap::new();
        let mut nxt = vec![0; n];
        let mut f = vec![-1_i64; n];

        for i in 0..n {
            *cnt.entry(power[i]).or_insert(0) += 1;
            let j = match power[i + 1..].binary_search_by(|&x| x.cmp(&(power[i] + 2 + 1))) {
                Ok(pos) | Err(pos) => i + 1 + pos,
            };
            nxt[i] = j;
        }

        fn dfs(
            i: usize,
            n: usize,
            power: &Vec<i32>,
            nxt: &Vec<usize>,
            f: &mut Vec<i64>,
            cnt: &HashMap<i32, i32>,
        ) -> i64 {
            if i >= n {
                return 0;
            }
            if f[i] != -1 {
                return f[i];
            }
            let c = *cnt.get(&power[i]).unwrap();
            let a = dfs(i + c as usize, n, power, nxt, f, cnt);
            let b = power[i] as i64 * c as i64 + dfs(nxt[i], n, power, nxt, f, cnt);
            f[i] = a.max(b);
            f[i]
        }

        dfs(0, n, &power, &nxt, &mut f, &cnt)
    }
}



// Solution 2
use std::collections::HashMap;

impl Solution {
    pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
        power.sort();
        let n = power.len();
        let mut cnt = HashMap::new();
        let mut nxt = vec![0; n];

        for i in 0..n {
            *cnt.entry(power[i]).or_insert(0) += 1;
            let j = match power[i + 1..].binary_search_by(|&x| x.cmp(&(power[i] + 2 + 1))) {
                Ok(pos) | Err(pos) => i + 1 + pos,
            };
            nxt[i] = j;
        }

        let mut f = vec![0_i64; n + 1];
        for i in (0..n).rev() {
            let c = *cnt.get(&power[i]).unwrap();
            let j = i + c as usize;
            let a = if j <= n { f[j] } else { 0 };
            let b = power[i] as i64 * c as i64 + f[nxt[i]];
            f[i] = a.max(b);
        }
        f[0]
    }
}

3186 - Maximum Total Damage With Spell Casting

3186. Maximum Total Damage With Spell Casting

Description

Solutions

Solution 1: Binary Search + Memoization

Solution 2: Binary Search + Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

3186. Maximum Total Damage With Spell Casting

Description

Solutions

Solution 1: Binary Search + Memoization

Solution 2: Binary Search + Dynamic Programming

All Problems

All Solutions