Максимизируйте сумму подмассивов заданного массива, добавив X в диапазоне [L, R] для запросов Q

Опубликовано: 20 Сентября, 2022

Учитывая массив arr[] из N целых чисел и M запросов на обновление типа (L, R, X) , задача состоит в том, чтобы найти максимальную сумму подмассива после каждого запроса на обновление, где в каждом запросе добавить целое число X к каждому элементу массива. массив arr[] в диапазоне [L, R] .

Примеры:

Input: arr[] = {-1, 5, -2, 9, 3, -3, 2}, query[] = {{0, 2, -10}, {4, 5, 2}}
Output: 12 15
Explanation: Below are the steps to solve the above example:

  • The array after 1st update query becomes arr[] = {-11, -5, -12, 9, 3, -3, 2}. Hence the maximum subarray sum is 12 of the subarray arr[3… 4].
  • The array after 2nd update query becomes arr[] = {-11, -5, -12, 9, 5, -1, 2}. Hence the maximum subarray sum is 15 of the subarray arr[3… 6].

Input: arr[] = {-2, -5, 6, -2, -3, 1, 5, -6, 4, -1}, query[] = {{1, 4, 3}, {4, 5, -4}, {7, 9, 5}}
Output: 16 10 20

Подход: Данную задачу можно решить с помощью алгоритма Кадане. Для каждого запроса обновляйте элементы массива, проходя по всем элементам массива arr[] в диапазоне [L, R] и добавляя целое число X к каждому элементу. После каждого запроса на обновление вычисляйте максимальную сумму подмассива, используя обсуждаемый здесь алгоритм.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ