i-м написано число stones[i]. Лягушка стоит на камне 0 и должна добраться до последнего. Прыгать можно только вперёд: с камня i на любой камень j > i, и за такой прыжок она получает (j - i) · stones[j] очков — длина прыжка, умноженная на число на камне приземления.
Верните наибольшую сумму очков, которую лягушка может набрать, добравшись до последнего камня.
Камней может быть до 10⁵, так что перебор всех пар «откуда — куда» за O(n²) не успеет. Нужно решение за линейное время.stones=[2, 6, 3, 5] → 16
Выгоднее всего прыгнуть 0 → 1 → 3: 1 · 6 + 2 · 5 = 16. Например, прыжок сразу 0 → 3 даёт только 3 · 5 = 15.
stones=[9, 1, 1] → 2
Значение первого камня в счёт не идёт. Оба маршрута, 0 → 2 и 0 → 1 → 2, дают 2.
stones=[2, 6, 3, 5]
16
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 109 тестов на сервере, включая скрытые.