Skip to content

3186. Maximum Total Damage With Spell Casting 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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])