наибольшая минимальная разница n элементов в массиве

Question

Учитывая массив A и число N.

Выберите N элементов из массива A так, чтобы минимальная разница между этими N числами была максимальной. Верните наибольшую минимальную разницу.

Пример 1. A = {1,2,4,8,9}, N = 3

Выход: 3 ( потому что {1,4,9} максимизирует разницу между этими 3 числами. 4-1 = 3, 9-4 = 5)

Example2. A = {4, 1,2,8,90,900}, N = 4

Вывод: 7

Это вопрос из курса по структуре данных, я боролся с этим вопросом для целый день, я надеюсь, что кто-нибудь может помочь мне с этим. Спасибо!

Answer 1

У нас может быть наивная динамическая c программа с O(n * log(n) * N) сложностью времени, где n - количество элементов в A. Предполагая, что массив отсортирован, пусть f(i, k) представляет наибольшую минимальную разницу в оптимальном решении для k элементов, выбранных от первого до i-го элемента, затем:

f(i, k) ->
  max(min(A[i] - A[j], f(j, k - 1)))

for all k - 2 ≤ j < i

Так как A[i] - A[j] не увеличивается и f(j, k - 1) не уменьшается при увеличении j, меньшее из них представляет унимодальную функцию, поэтому мы можем двоично искать оптимальный j на каждой итерации.

Answer 2

1. Сортировка массива
2. Для N = 2 на выходе будут значения в [0] и [n], где 0 и n - индексы массива (n - длина массива )
3. Для N = 3 0, n и n / 2 (если n нечетно, вам нужно проверить, что лучше n / 2 и n / 2 + 1) и разбить массив на 2
4. Для N = 4 вам нужно проверить, какая "медиана" из 2 массивов дает наилучший результат.
5. Я думаю, что вы получите его, всегда делите каждую половину на 2.

Сложность: n * log (n) для сортировки + N (для проверки + разбиение)