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

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

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

Примечание. Любой элемент массива можно добавить не более одного раза.

Примеры:

Input: arr[] = {3, 9, 19, 5, 21}, M = 10
Output: 67
Explanation: One way to getthe value is
M > 3; 3 is added to M and it becomes 10+3 = 13
M > 9; 9 is added to M and it becomes 13+9 = 22
M > 19; 19 is added to M and it becomes 22+19 = 41
M > 5; 5 is added to M and it becomes 41+5 = 46
M > 21; 21 is added to M and it becomes 46+21 = 67
Thus, M = 67 at the end.

Input: arr[] = {2, 13, 4, 19}, M = 6
Output: 12
Explanation: One way to get the value is
M > 4; 4 is added to M and it becomes 6+4 = 10
M > 2; 2 is added to M and it becomes 10+2 = 12
No other value in the array is smaller or equal to M.
Thus, M is 12 at the end.

Подход: Решение основано на концепции сортировки. Выполните шаги, указанные ниже:

  • Сначала отсортируйте массив в порядке возрастания.
  • Для каждого индекса i от 0 до N-1 сделайте следующее:
    • Если M ≥ arr[i] , добавить arr[i] с M .
    • Если M< arr[i] , остановите итерацию.
  • Верните окончательное значение M в качестве ответа.

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


Временная сложность: O(N * logN)
Вспомогательный пробел: O(1), так как дополнительный пробел не добавлялся.

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