Максимизируйте сумму массива после изменения знака любых элементов ровно M раз

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

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

Примеры:

Input: arr[ ] = {-3, 7, -1, -5, -3}, M = 4
Output: 19
Explanation:
4 operations on the array can be performed as, 
Operation 1: Change the sign of arr[0] -> {3, 7, -1, -5, -3}
Operation 2: Change the sign of arr[2] -> {3, 7, 1, -5, -3}
Operation 3: Change the sign of arr[3] -> {3, 7, 1, 5, -3}
Operation 4: Change the sign of arr[4] -> {3, 7, 1, 5, 3}
The maximum sum of array obtained is 19.

Input: arr[ ] = {-4, 2, 3, 1}, M = 3
Output: 10   

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

  • Инициализируйте очередь с минимальным приоритетом, скажем, pq[], и поместите все элементы массива arr[].
  • Инициализируйте переменную, скажем, sum = 0, чтобы сохранить максимальную сумму массива.
  • Повторите цикл while, пока M не станет больше 0 , и выполните следующие действия:
    • Вытолкните из очереди приоритетов и вычтите из переменной sum .
    • Переверните знак выталкиваемого элемента, умножив его на -1 и прибавив к сумме .
    • Поместите новый перевернутый элемент в приоритетную очередь и вычтите 1 из M .
  • Наконец, выведите максимальную сумму, хранящуюся в переменной sum .

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


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

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