Последовательность чисел с ограничениями

Question

У меня есть последовательность положительных чисел x_1, x_2, ... X_n и я хочу, чтобы найти последовательную подпоследовательности, где: 0 < x_i-X_j < IJ, 1 < = у < < я = п выполняется для всех i, j. Определите S (t) как длину самой длинной последовательной последовательности, заканчивающуюся на x_t ..

например. если S (t) = 3, то это справедливо для x_t, x_ {t-1}, x_ {t-2}

Я пытаюсь найти формулу рекурсии, и я полностью застрял. Я попытался немного поиграть с цифрами, чтобы найти какой-то рисунок:

S (5) = 2 означало бы, что S (5) = 2 + S (4) и S (4) должны быть $ 0 $. Но то возможно, что S (3) может быть равным 1, поэтому мы должны остановиться, как только выясним, что S (4) = 0

Базовые чехлы или, возможно, специальные случаи S (0) = 0, S (1) = 0?

Можно ли написать S (k) в терминах S (k-1)?

Я пытаюсь построить алгоритм для этого, но сначала мне нужно выяснить формулу рекурсии.

Answer 1

S (0) = 0
Если (x_n < = X_ {N-1} или X_n - X_ {п-1}> = 1) => S (N) = 0
еще, если S (n-1) = 0 => S (n) = 2
else S (n) = S (n-1) + 1

Answer 2

Нет необходимости в динамическом программировании или рекурсии в этой проблеме из-за простого отношение оператора сравнения: оно транзитивно. Это означает, что:

a < b and b < c => a < c 

Мы можем превратить это неравенство немного:

x_i - x_j < i - j 
x_i - i < x_j - j 

Это делает всю проблему намного проще:
Определить последовательность y, где y_i = x_i - i. Найдите самую длинную строго убывающую последовательность, заканчивающуюся на y_t.

Из-за транзитивности в строго убывающей последовательности ваше условие всегда выполняется и наоборот. Фактически эти два ограничения эквивалентны в этом случае, так как не может быть ограничение, которое одновременно уменьшается и не нарушает ограничений на последовательность. Таким образом, в этом случае нет необходимости в рекурсии, так как линейная связь вполне достаточна (транзитивность).

Конечно, вы могли бы перевести этот поиск первого неубывающей пары в рекурсивной функции (хотя это гораздо сложнее, чем просто идти по линейному пути):

S(t) = {t = 0:        0 
     t = 1:        1 
     {x_t - t >= x_{t-1} - (t - 1)}: 1 
     else:        1 + S(t - 1)}