Subarray with given length and maximum sum

Revision en4, by Honey_Badger, 2020-09-22 21:03:24

I solved this problem using binary search the answer, substracting it from each element of the array and finding its subarray with the largest sum. Then I came up with a different approach: we can iterate through possible lenghts of a subarray, pick one with the largest sum and update the answer. However, I don't know how to implement finding a subarray with length = 1..n and maximum sum fast enough to pass all tests.

Tags usaco

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)