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

😎 Решение:

function deleteAndEarn($nums) {
    $count = array_count_values($nums);
    $avoid = $using = 0;
    $prev = -1;
    
    ksort($count);
    foreach ($count as $num => $freq) {
        if ($num - 1 != $prev) {
            $newAvoid = max($avoid, $using);
            $using = $num * $freq + max($avoid, $using);
            $avoid = $newAvoid;
        } else {
            $newAvoid = max($avoid, $using);
            $using = $num * $freq + $avoid;
            $avoid = $newAvoid;
        }
        $prev = $num;
    }
    
    return max($avoid, $using);
}

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