Самый большой минимум массива в операциях N-1 путем уменьшения каждого элемента на минимум
Учитывая массив 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))
Следовательно, конечным результатом будет максимальная разница двух последовательных элементов, как видно из приведенного выше доказательства. Выполните следующие шаги, чтобы решить проблему:
- Создайте переменную max_value для хранения окончательного ответа и инициализируйте его с помощью arr[0] .
- Отсортируйте массив arr[] по возрастанию.
- Запустите цикл от i=0 до i<(N-1) и на каждой итерации:
- Отслеживайте максимальное или минимальное значение (т. е. разницу arr[i + 1] — arr[i] ) на каждой итерации. Итак, сделайте max_value максимальным из max_value и (arr[i+1] – arr[i]) .
- Верните max_value в качестве окончательного ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(NlogN)
Вспомогательное пространство: O(1)