Удалить и заработать

Источник: https://leetcode.com/problems/delete-and-earn/

Дан массив nums целых чисел.

Из массива можно удалить эементnums[i] и заработать nums[i] очков. После чего нужно удалить все элементы равные nums[i] - 1 или nums[i] + 1.

Перед проведением операци йдаления у вас 0 очков. Вернуть максимальное значение очков, которые можно заработать, применяя операцию "удалить и заработать", описанную выше.

Пример 1:

Дано: nums = [3,4,2]
Результат: 6
Пояснение: Удялем и зарабатываем 4, затем 3 тоже удаляем, поскольку 3=4-1. Остается [2]. Удаляем 2 и зарабатываем +2. Итого 4+2=6.

Пример 2:

Дано: nums = [2,2,3,3,3,4]
Результат: 9
Пояснение: Удаляем и зарабатываем 3. 2=3-1 и 4=3+1 - удаляем ВСЕ 2 и 4. Остается [3,3]. Удаляем и зарабатываем +3, но больше нет соседних значений (2 и 4). Остается [3]. Удалеям и зарабатываем ещё раз +3. Итого 3+3+3=9.

Огранияения:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

Идея решения

Заметим, что если в массиве есть дубликаты, то если мы можем взять хотя бы один из них, то мы можем взять их все. Потому что после взятия первого элемента из одинаковых мы удаляем всех его сосдей и спокойно добираем остальные дубликаты.

Поэтому просуммируем дубликаты и расположим их в ячейках с индексом, соответсвующим их значению. Для примера 2 мы получим: [ 0*0, 1*0, 2*3, 3*3, 4]=[0, 0, 0, 6, 9, 4]

Если мы возьмем значение в ячейке 3 (оно равно 9), то мы не можем взять знаяения в яяейках 2 и 4, но можем взять всё, что идет до 2 и после 4. На самом деле, мы можем просуммировать 3 с накоплениями до 2, если эта сумма больше, чем накопления в 2. А потом просуммировать 5 (если бы была такая ячейка) с накоплениями в 3 или взять накопления в 4. Таким образом, у нас жадный алгоритм + динамическое программирование по формуле.

sum[i] = Max(sum[i-1], sum[i-2] + sum[i])

За линейное время мы можем просканировать массив с суммами за линейное время. В ячейке n+1 (хоть у нас массив и имеет макимальный элемемент n) в итоге окажется максимальное значение от операций.

Имплементация

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[10002];  // максимальное значение<=  10000
//  то есть нам нужно 10001 элемент в массиве + накидываем ещё один для доп рассчетов
       
// для каждого значения считаем, сколько мы на нем можем заработать, если оно продублировано
        for(int i = 0; i < nums.length; i++){
            sum[nums[i]] += nums[i]; // из примера 2: [ 0, 0, 2*3, 3*3, 4, 0]=[0, 0, 0, 6, 9, 4, 0]
        }
    
// в индексе 0 мы можем заработать 0
// в индексе 1 мы можем заработать только его содержимое
// поэтому начнием рассматривать с индекса 2 
         for(int i = 2; i < sum.length; i++){
// если мы возьмем значения в текущей ячейке,
// то мы не можем взять накопленное из предыдущей
// (предыдщуая=текущая-1 и ее нужно удалить),
// но мы можем взять накопленное в предыдущей от предыдущей;
//  поэтому выбираем максимальный вариант между:
// предыдущая ИЛИ ткущая + предыдущая предыдущей
            sum[i] = Math.max(sum[i-1], sum[i-2] + sum[i]);
        }
        return sum[10001];
    }
} 

Сложность алгоритмя: O(n)