Максимальная прибыль, которую можно получить, купив не более K книг

Даны целое число K и массив arr[] , состоящий из N целых чисел, где элемент массива arr[i] представляет цену i ^-й книги. Прибыль от покупки i ^-й книги представляет собой max(0, -1 * arr[i]) , задача состоит в том, чтобы найти максимальную прибыль, возможную при покупке не более K книг.

Примеры:

Input: arr[] = {-10, 20, -30, 50, -19}, K = 2
Output: 49
Explanation: 
Maximum profit can be obtained by buying the books arr[2](= -30). Profit = 30 and the book, arr[4](= -19) for the profit of 19.
Therefore, the total maximum profit obtained is, (30+19 = 49).

Input: arr[] = {10, 20, 16, 25}, K = 3
Output: 0

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

• Отсортируйте массив arr[] по возрастанию.
• Инициализируйте переменную, скажем, maxBenefit как 0 , чтобы сохранить максимальную прибыль.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Если K больше 0 , а arr[i] отрицательное, добавьте abs(arr[i]) к maxBenefit, а затем уменьшите значение K на 1.
• Наконец, выведите значение maxBenefit как максимальную полученную прибыль.

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

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