Максимизируйте сумму массива после изменения знака любых элементов ровно M раз
Дан массив 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)