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

Revision ru1, by Honey_Badger, 2020-09-22 21:17:36

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English Honey_Badger 2020-09-22 22:43:28 9
en7 English Honey_Badger 2020-09-22 22:40:52 1
en6 English Honey_Badger 2020-09-22 22:40:30 4 Tiny change: 'sible lenghts of a suba' -> 'sible length of a suba'
ru2 Russian Honey_Badger 2020-09-22 22:33:22 189
en5 English Honey_Badger 2020-09-22 22:31:34 142
ru1 Russian Honey_Badger 2020-09-22 21:17:36 543 Первая редакция перевода на Русский
en4 English Honey_Badger 2020-09-22 21:03:24 2 Tiny change: 'enghts of subarray,' -> 'enghts of a subarray,'
en3 English Honey_Badger 2020-09-22 21:02:07 30 Tiny change: 'aximum sum. ' -> 'aximum sum fast enough to pass all tests. '
en2 English 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 English Honey_Badger 2020-09-22 20:58:25 499 Initial revision (published)