максимум минимума разницы в подпоследовательности размера k

Question

Дана отсортированная последовательность из n элементов. Найти максимум всех минимумов, взятых из всех пар разностей подпоследовательностей длины k.

Here 1<=n<=10^5
and 2<=k<=n

For eg: [2, 3, 5, 9] and k = 3
there are 4 subsequences:

[2, 3, 5] - min diff of all pairs = 1
[2, 3, 9] - min diff of all pairs = 1
[3, 5, 9] - min diff of all pairs = 2
[2, 5, 9] - min diff of all pairs = 3

Таким образом, ответ является максимальным из всех min diffs = 3

Наивный способ состоит в том, чтобы найти все подпоследовательности длины k, а затем найти минимумы в каждой из них, а затем максимум всех из них, но это время истечет из-за ограничений.

Помимо того, что я думал, было найти последовательность, которая оптимально удалена так, чтобы минимум стал максимальным.

Может кто-нибудь дать оптимальное и лучшее решение?

Answer 1

Предположим, что ваша последовательность целых чисел a[i]. Тогда мое решение найдет ответ вовремя O(n log((a[n-1]-a[0])/n)). Если ваша последовательность состоит из чисел с плавающей запятой, она, вероятно, будет выполняться в то же время, но теоретически может быть такой же плохой, как O(n^3).

Ключевое наблюдение таково. Легко построить самую компактную последовательность, начиная с первого элемента, минимальный зазор которого составляет не менее m. Просто возьмите первый элемент и возьмите друг друга, когда он будет как минимум на m больше, чем последний, который вы взяли. Таким образом, мы можем написать функцию, которая создает эту последовательность и отслеживает 3 числа:

1. Сколько элементов мы получили
2. Размер наименьшего зазора, который мы нашли.
3. Следующий наименьший m, который приведет к более компактной последовательности. Это самый большой пробел в элементе, который мы не включили.

В случае вашей последовательности, если мы сделали это с пробелом 2, мы обнаружили бы, что мы взяли 3 элемента, наименьший пробел равен 3, и мы получили бы другую последовательность, если бы мы искали пробел 1.

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

lower_bound = 0
upper_bound = (a[n-1] - a[0])/(k-1)
while lower_bound < upper_bound:
    # Whether int or float, we want float to land "between" guesses
    guess = (lower_bound + upper_bound + 0.0) / 2
    (size, gap_found, gap_different) = min_gap_stats(a, guess)
    if k < size:
        # We must pick a more compact sequence
        upper_bound = gap_different
    else:
        # We can get this big a gap, but maybe we can get bigger?
        lower_bound = gap_found

Если бы мы запустили это для вашей последовательности, мы сначала установили бы lower_bound в 0 и upper_bound в 7/2 = 3 (благодаря целочисленному делению). И мы сразу найдем ответ.

Если бы у вас была последовательность чисел с одинаковыми значениями, это заняло бы больше времени. Сначала мы попробуем 3,5, и получим последовательность 2 с другим решением на 3. Затем мы попробуем 1,5 и найдем нашу последовательность 3 с желаемым промежутком.

Бинарный поиск обычно делает логарифмическое число проходов. Однако каждый раз мы устанавливаем верхнюю или нижнюю границу для размера фактического попарного разрыва. Поскольку есть только O(n^2) пробелов, нам гарантировано, что нам потребуется не больше, чем столько проходов.