Уменьшите данный массив до 0, максимизировав сумму выбранных элементов

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

Примечание . Значение любого элемента массива не может быть меньше 0.

Примеры:

Input: arr[] = {6, 2, 4, 5} 
Output: 12
Explanation: Add 6 initially to the final sum.
The final sum becomes 6 and the remaining array elements {1, 3, 4}.
Add 3 with the sum. The sum becomes 9 and the remaining elements {0, 3}
Add 3 with the sum. The sum becomes 12 and only 0 remains in the array.
Add 0 with the sum. The sum remains unchanged.

Input: arr[] = {5, 6, 4}
Output: 12

Наивный подход: найти максимальный элемент массива. Добавьте его к сумме и уменьшите все остальные элементы на 1 и измените текущий элемент на 0, чтобы он больше не повторялся в цикле. Делайте этот процесс, пока все элементы не станут 0.

Временная сложность: O(N ² )

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

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

• Отсортируйте массив в порядке убывания .
• Запустите цикл от 1 до N .
  • Для каждого индекса i значение, добавленное к окончательной сумме, будет (arr[i] – i) , так как оно будет добавлено после i уменьшения значения.
  • Поскольку значение суммы не может быть меньше 0 , добавьте max(arr[i]-i, 0) к окончательной сумме.
• Верните окончательную сумму.

Ниже приведена реализация описанного выше подхода.

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