values длины n и **нечётное** число k. Выберите ровно k непустых непересекающихся отрезков (подряд идущих элементов) piece₁, piece₂, …, pieceₖ, идущих слева направо: каждый следующий начинается правее, чем заканчивается предыдущий. Покрывать весь массив не обязательно.
Сила выбора считается так:
k · sum(piece₁) − (k − 1) · sum(piece₂) + (k − 2) · sum(piece₃) − … − 2 · sum(pieceₖ₋₁) + 1 · sum(pieceₖ)
то есть у куска номер j вес k − j + 1, а знаки чередуются, начиная с плюса. Верните наибольшую возможную силу.values=[3, -2, 4], k=3 → 17
Весы кусков: 3, −2, 1. Каждый кусок — один элемент: 3 · 3 − 2 · (−2) + 1 · 4 = 17.
values=[2, 5, -1, 3], k=1 → 9
Один кусок с весом 1 — берём весь массив: 2 + 5 − 1 + 3 = 9.
values=[1, -4, 2, 2, -3], k=3 → 15
Куски [1], [−4] и [2, 2]: 3 · 1 − 2 · (−4) + 1 · 4 = 15. Последний элемент −3 в выбор не входит.
k нечётноеvalues=[3, -2, 4], k=3
17
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 111 тестов на сервере, включая скрытые.