Сложность: medium
Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.
Пример:
Input: nums = [3,4,2]
Output: 6
👨💻 Алгоритм:
1⃣Подсчитайте количество каждого числа в массиве nums.
2⃣Используйте динамическое программирование для расчета максимальных очков, которые можно заработать, используя накопленный результат для чисел, меньших текущего. Добавьте текущий день в стек.
3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.
😎 Решение:
def deleteAndEarn(nums):
from collections import Counter
count = Counter(nums)
prev = None
avoid = using = 0
for num in sorted(count):
if num - 1 != prev:
new_avoid, new_using = max(avoid, using), num * count[num] + max(avoid, using)
else:
new_avoid, new_using = max(avoid, using), num * count[num] + avoid
avoid, using = new_avoid, new_using
prev = num
return max(avoid, using)
Ставь 👍 и забирай 📚 Базу знаний