Задачи
January 29

Задача. Максимальное количество очков

Задача: дан массив целых чисел. Необходимо максимизировать количество очков, которые вы получаете, выполняя следующую операцию любое количество раз:

Если вы выберите любой элемент массива nums[i] и удалите его, то получите nums[i] очков. Но после этого вы также ДОЛЖНЫ удалить каждый элемент массива, равный (nums[i] - 1) и каждый элемент равный (nums[i] + 1). За эти элементы вы НЕ получаете очки.

Входные данные: размер исходного массива от 1 до 1000. Элементы массива - целые числа от 1 до 1000.

Примеры:

  1. [3, 4, 2]
    Output: 6
    Пояснение: удаляем 4 и получаем 4 очка, после этого мы обязаны удалить элемент 3. Остается последний элемент 2, мы его удаляем и получаем 2 очка.
  2. [2, 2, 3, 3, 3, 4]
    Output: 9
    Пояснение: удаляем элемент 3 и получаем 3 очка, дальше мы обязаны удалить все 2 и все 4. Остается [3, 3]. Поочередно удаляем оба этих элемента и получаем за каждый из них по 3 очка.

Разбор

Если вы помните, мы решали похожу задачу - Robber.
В нашем случае, если мы получаем очки с nums[i], тогда мы не сможем получить очки равные nums[i] - 1 и nums[i] + 1.

Тогда алгоритм будет следующий:

  1. Заведем массив значений, по размеру равный нашим ограниченями в 1000 элементов.
  2. Все исходные элементы занесем по правилу count[num] = num.
  3. Далее создадим 3 счетчика: previous, current, next.
  4. Тогда счетчик next будем заполнять по формуле, которые мы определили выше:
    next = Math.Max(previous + count[i], current).
  5. Обновляем счетчики previous, current.
  6. Возвращаем значение счетчика next.

Реализация

Play-test

https://dotnetfiddle.net/ouXBSu