Выбор номеров для максимального интервала

Question

Существует массив, содержащий число от 0 до 999 в строго возрастающем порядке.

Например

int[] array = {0, 24, 55, 124, 200, 259, 400, 503, 666, 797}; 

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

Например, если N равно 3, то выбранные числа - 0, 400, 797, а интервалы - 400 и 397; поэтому возвращаемое значение равно 397 (которое должно быть увеличено). Если мы выберем другие наборы чисел, тогда возвращаемое значение будет меньше (или равно) 397.

Я хотел бы реализовать его с помощью рекурсии, но мне сложно его кодировать. Вы хотите мне помочь?

Answer 1

Эта проблема может быть решена с использованием dynamic programing.

Если мы определим s[c][p] решением при наборе c номеров, а последнее выбранное число имеет индекс p в массиве ввода.

Мы можем затем вычислить, как s[c][p]max for i=0..p of max(s[c-1][p-i], array[p] - array[p-i])

В начале следующих состояний: s[1][0..n], где n является длиной входного массива, должны иметь значение 0.

Имея s[1][0..n], мы теперь можем легко вычислить s[2][0..n], используя данную формулу.
Имея s[2][0..n], мы теперь можем легко вычислить s[3][0..n].
И так далее ...

Решение всей проблемы было бы max s[N][N-1..n] где n длина входного массива и N это количество чисел, чтобы выбрать.

Сложность этого решения составляет O(N*n^2).
Объяснение: Рассчитываем значения для s[0..N][0..n], где каждый расчет имеет временную сложность O(n).

Сложность этого решения составляет O(n).
Объяснение: для расчета s[c][0..n] вам нужен только s[c-1][0..n], так что только 2*n памяти действительно необходимо в каждый момент времени.

EDIT: вы можете использовать рекурсию для реализации описанного алгоритма, используя технологию программирования, называемую memoization (https://en.wikipedia.org/wiki/Memoization).