Как найти максимальную сумму подмассива размера между [L, R]

Question

Учитывая массив как положительных, так и отрицательных целых чисел, как найти подмассив максимальной суммы (непрерывный подмассив) длиной от L до R включительно?

Например: если массив

-1 3 -2 5 3 -5 2 2

и L = 1 и R = 2, ответ будет 8.

Мой подход:

Я не слишком уверен, как подойти к этому вопросу. Подумал, может это комбинация раздвижного окна + кадана. Я слышал, что сумма префиксов + скользящее окно может быть возможным решением, но я не уверен, как это реализовать.

Answer 1

Если я правильно понимаю вашу проблему, существует решение n * logn, которое действительно использует суммы префиксов и скольжение windows. Здесь объясняется: https://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-l-r/