Максимизируйте сумму подмассивов, выбрав M подмассивов размера K

Дан массив arr , содержащий N положительных целых чисел, и два целых числа K и M. Задача состоит в том, чтобы вычислить максимальную сумму M подмассивов размера K.

Пример:

Input: arr[] = {1, 2, 1, 2, 6, 7, 5, 1}, M = 3, K = 2
Output: 33
Explanation: The three chosen subarrays are [2, 6], [6, 7] and [7, 5] respectively. So, sum: 8 +12 +13 = 33

Input: arr[] = {1, 4, 1, 0, 6, 7, 5, 9}, M = 4,, K = 5
Output: 76

Подход: проблема может быть решена путем предварительного вычисления суммы префиксов до каждого индекса i , который сообщит нам сумму подмассива от 0 до i . Теперь эту сумму префиксов можно использовать для нахождения суммы каждого подмассива размера K по формуле:

Subarray sum from i to j = Prefix sum till j – prefix Sum till i

Найдя сумму всех подмассивов, выберите максимальные суммы M подмассивов для вычисления ответа.
Чтобы решить эту проблему, выполните следующие действия:

1. Создайте вектор prefixSum, в котором каждый узел представляет сумму префикса до этого индекса, и другой вектор subarraySum для хранения суммы всех подмассивов размера K.
2. Теперь запустите цикл от i=K до i=N и вычислите сумму каждого подмассива, используя формулу subarraySum[iK, i] = prefixSum[i]-prefixSum[iK] и поместите ее в векторный subarraySum .
3. Отсортируйте subarraySum в порядке убывания и добавьте M верхних элементов, чтобы получить ответ.
4. Выведите ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)