Максимальное произведение массива после вычитания 1 из любого элемента N раз

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

Примеры :

Input: M = 5, arr[] = {5, 1, 7, 8, 3}, N = 2
Output: 630
Explanation: After subtracting 1 from arr[3] 2 times, array becomes {5, 1, 7, 6, 3} with product = 630
Input: M = 2, arr[] = {2, 2}, N = 4
Output: 0
Explanation: After subtracting 2 from arr[0] and arr[1] 2 times each, array becomes {0, 0} with product = 0

Подход : Задача может быть решена с помощью max-heap Выполните следующие шаги, чтобы решить проблему:

• Вставьте все элементы в максимальную кучу
• Извлеките верхний элемент из max-heap и уменьшите его на 1, а также уменьшите N
• Вставьте выскочивший элемент обратно в max-heap
• Продолжайте этот процесс, пока N > 0
• Максимальный продукт будет произведением всех элементов внутри максимальной кучи.

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

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