Войти Регистрация
Алгоритмы

90. Дни отметок в акции с баллами

Сложная

Акция в приложении Т-Банка идёт n дней. Отметка в день i приносит points[i] баллов; в дни с платной подпиской баллы отрицательные — это списание.

Клиент обязан отметиться в день 0 и в последний день, а между соседними отметками может пройти не больше k дней (из дня i можно перейти в дни i+1 … i+k). Верните максимальную сумму баллов.

В работе: ДП, где переход берёт максимум по окну последних k состояний: расписания, прыжки с ограничением шага.

Пример 1

Ввод
points = [10, -5, -2, 4, 0, 3]
k = 3
Вывод
17

Дни 0, 3, 4, 5: 10 + 4 + 0 + 3 = 17.

Пример 2

Ввод
points = [-3]
k = 1
Вывод
-3

Один день — он же первый и последний.

Ограничения

  • 1 ≤ длина points ≤ 10⁵
  • 1 ≤ k ≤ 10⁵
  • -10⁴ ≤ points[i] ≤ 10⁴
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def max_checkin_points(points, k):
ДПМонотонная очередьСкользящий максимумцельO(n)

Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.