Подотрезок заданной длины с максимальной суммой

Правка ru1, от Honey_Badger, 2020-09-22 21:17:36

Я решил эту задачу, используя бинпоиск по ответу. Для проверки я отнимал значение от всех элементов и проверял, что сумма массива без подотрезка с максимальной суммой не больше нуля. Потом я придумал другой подход: переберем длину убираемого отрезка, найдем в массиве подотрезок этой длины с максимальной суммой, обновим ответ. Как можно эффективно для каждой длины от 1 до n найти подотрезок массива такой длины с максимальной суммой?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский Honey_Badger 2020-09-22 22:43:28 9
en7 Английский Honey_Badger 2020-09-22 22:40:52 1
en6 Английский Honey_Badger 2020-09-22 22:40:30 4 Tiny change: 'sible lenghts of a suba' -> 'sible length of a suba'
ru2 Русский Honey_Badger 2020-09-22 22:33:22 189
en5 Английский Honey_Badger 2020-09-22 22:31:34 142
ru1 Русский Honey_Badger 2020-09-22 21:17:36 543 Первая редакция перевода на Русский
en4 Английский Honey_Badger 2020-09-22 21:03:24 2 Tiny change: 'enghts of subarray,' -> 'enghts of a subarray,'
en3 Английский Honey_Badger 2020-09-22 21:02:07 30 Tiny change: 'aximum sum. ' -> 'aximum sum fast enough to pass all tests. '
en2 Английский Honey_Badger 2020-09-22 20:59:29 6 Tiny change: 'm. Then I tried came up w' -> 'm. Then I came up w'
en1 Английский Honey_Badger 2020-09-22 20:58:25 499 Initial revision (published)