Самый большой минимум массива в операциях N-1 путем уменьшения каждого элемента на минимум

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

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

Примеры:

Input: arr[] = {-1, -2, 4, 3, 5}
Output: 4
Explanation: Following are the operations performed:
Operation 1: Remove -2 and subtract it from remaining. Now array arr[] becomes {1, 6, 5, 7}. minimum element =1, max minimum element = 1.
Operation 2: Remove 1 and subtract it from remaining. Now array arr[] becomes {5, 4, 6}. minimum element =4, max minimum element = 4.
Operation 3: Remove 4 and subtract it from the remaining. Now arr[] becomes {1, 2}. minimum element =1 max minimum element = 4 till now.
Operation 4: Remove 1 and subtract it from remaining. Now arr[] becomes {1}. minimum element = 1, max minimum element = 4 till now
Therefore, Maximum minimum element is 4.

Input: arr[] = {-3, -1, -6, -7}
Output: 3

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

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

Эффективный подход. Описанный выше подход можно оптимизировать с помощью жадного подхода. Это может быть получено математически, поскольку минимальный элемент необходимо удалять каждый раз, и поэтому он не зависит от порядка элементов в массиве. Итак, массив нужно отсортировать. Следуйте приведенному ниже наблюдению, чтобы решить проблему:

Since the Minimum element needs to be removed in each operation. Consider the array after sorting in increasing order is {a1, a2, a3, a4, a5, …}
Initially a1 is the minimum and after removing it, the array becomes {a2-a1, a3-a1, a4-a1, a5-a1, …}
Now a2-a1 is the minimum and after removing it, the array becomes {a3-a1-(a2-a1), a4-a1-(a2-a1), …} which is equal to {a3-a2, a4-a2, a5-a2, …}
Now a3-a2 is the minimum and it continues so…
So, res = max(a1, ∑(i=0 to (N-1)) (ai+1 -ai))

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

  1. Создайте переменную max_value для хранения окончательного ответа и инициализируйте его с помощью arr[0] .
  2. Отсортируйте массив arr[] по возрастанию.
  3. Запустите цикл от i=0 до i<(N-1) и на каждой итерации:
    • Отслеживайте максимальное или минимальное значение (т. е. разницу arr[i + 1] — arr[i] ) на каждой итерации. Итак, сделайте max_value максимальным из max_value и (arr[i+1] – arr[i]) .
  4. Верните max_value в качестве окончательного ответа.

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


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

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