Задача: 740. Delete and Earn
Сложность: 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, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

var deleteAndEarn = function(nums) {
    const count = {};
    nums.forEach(num => count[num] = (count[num] || 0) + 1);
    
    let prev = null;
    let avoid = 0, using = 0;
    
    Object.keys(count).sort((a, b) => a - b).forEach(num => {
        num = parseInt(num);
        if (num - 1 !== prev) {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + Math.max(avoid, using);
            avoid = newAvoid;
        } else {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + avoid;
            avoid = newAvoid;
        }
        prev = num;
    });
    
    return Math.max(avoid, using);
};

Ставь 👍 и забирай 📚 Базу знаний