Ctrl K

Заклинания без соседей

Средняя
У волшебника есть набор заклинаний, damage[i] — урон i-го. У нескольких заклинаний урон может совпадать. Каждое заклинание можно применить не больше одного раза. Но если волшебник применил заклинание с уроном x, он уже не может применять заклинания с уроном x - 2, x - 1, x + 1 и x + 2. Заклинания с тем же уроном x при этом разрешены. Верните наибольший суммарный урон, который можно нанести.
Пример 1
damage=[2, 2, 4, 5, 9] → 18

Берём обе двойки, пятёрку и девятку: 2 + 2 + 5 + 9 = 18. Четвёрку взять нельзя — она отличается от 2 и от 5 не больше чем на 2.

Пример 2
damage=[3, 4, 5, 6] → 9

Любые два числа здесь отличаются не больше чем на 3; совместимы только 3 и 6, их сумма 9.

Пример 3
damage=[10] → 10
Ограничения
  • 1 ≤ len(damage) ≤ 10⁵
  • 1 ≤ damage[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПары с заданной разницей СредняяСлова, спрятанные в тексте СредняяТройки с точной суммой СредняяСлово растёт по букве СредняяЗаработок водителя маршрутки Средняя
загружаем Python…
Вход
damage=[2, 2, 4, 5, 9]
Ожидается
18

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 102 теста на сервере, включая скрытые.