Найдите подпоследовательность размера k такую, чтобы минимальное расстояние между значениями было максимальным - PullRequest
Новая
       65

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

0 голосов
/ 26 мая 2020

Предположим, у меня есть последовательность random ( массив упорядочения ), которая содержит n положительное число с плавающей запятой. Как найти подпоследовательность размера k , чтобы минимальное расстояние между всеми парами чисел с плавающей запятой в подпоследовательности было максимальным, то есть они находятся на самом дальнем расстоянии.

Примечание : A подпоследовательность последовательности - это упорядоченное подмножество элементов последовательности, имеющих тот же порядок следования, что и исходная последовательность.

ОГРАНИЧЕНИЯ

  1. n> 10 ^ 5
  2. n> k> 2

пример :

последовательность a [] = {1.1,2.34,6.71,7.01,10.71} и k = 3, подпоследовательность = {1.1,6.71,10.71}, минимальное расстояние 4 между 10,71 и 6,71.

Неверная подпоследовательность :

{1.1,7.01,10.71}, минимальное расстояние составляет 3,7

{1.1,2.34,6.71}, минимальное расстояние составляет 1,24

Я придумал решение:

1) массив сортировки

2) выберите [0], теперь найдите ceil (a [0] + x) = Y в массиве ... ., а затем ceil (Y + x) и так k-1 раз, также k-й элемент будет быть [n-1]

Чтобы найти x:

dp [i, j] быть x для выбора j элементов из первых i элементов.

Наконец, мы хотим dp [n] [k], который равен x

Но я столкнулся с проблемой поиска x и изменения порядка индексов.

dp [i, j] = max (min (dp [k, j-1], dp [i] -A [k]))

от k = 1 до i-1, от i = 2 до n, j = 2 до i

dp [ i] [1] = 0 по i = от 1 до n

Я хочу исправить решение программирования Dynami c, хотя я знаю, что x можно найти с помощью двоичного поиска по x, но путем сортировки я теряю упорядочение последовательности и требует много времени ( O ( n ^ 2 )). Как мне решить эту проблему?

1 Ответ

1 голос
/ 26 мая 2020

Если есть решение, включающее сортировку, вы сначала хотите отобразить массив в массив кортежей, которые содержат значение и позицию элемента. Теперь, когда вы сортируете массив, вы также знаете исходные позиции.

Однако я не верю, что сортировка действительно поможет вам в конце.

Подход, который я вижу, который работает, предназначен для каждый 0 <= i < n, для каждого 1 < j <= min(k, i+1), чтобы сохранить минимальное расстояние и предыдущую запись для лучшей подпоследовательности длины j, заканчивающейся на i.

Затем вы ищите лучшую подпоследовательность длины k. А затем декодируйте подпоследовательность.

Используя нотацию JSON (для ясности, а не потому, что это правильная структура данных) и ваш пример, вы можете получить такую ​​структуру данных: 

[
    {"index": 0, "value": 1.1},
    {"index": 1, "value": 2.34,
        "seq": {2: {"dist": 1.34, "prev": 0}},
    {"index": 2, "value": 6.71,
        "seq": {2: {"dist": 5.61, "prev": 0},
                3: {"dist": 1.34, "prev": 1}},
    {"index": 3, "value": 7.01,
        "seq": {2: {"dist": 5.91, "prev": 0},
                3: {"dist": 1.34, "prev": 1}},
    {"index": 4, "value": 10.71,
        "seq": {2: {"dist": 9.61, "prev": 0},
                3: {"dist": 4, "prev": 2}}
]

И теперь мы обнаруживаем, что самый большой dist для длины 3 равен 3.7 с индексом 4. Возвращаясь назад, нам нужны индексы 4, 2 и 0. Вытяните их и переверните, чтобы получить решение [1.1, 6.71, 10.71]

...