длинное увеличение подпоследовательности [1 2 .. N] перестановка

Question

Вот проблема:

Дана массив из N элементов (от 1 до N), отсортировать массив с одним ограничением: вы можете только переместить элемент для начала массива или конца массива. Сколько ходов вам нужно, по крайней мере, отсортировать массив?

Например: 2 5 3 4 1 =>1 2 5 3 4 =>1 2 3 4 5, поэтому мне нужно как минимум 2 шага.

Я определяю одно решение: N - length of longest increasing subsequence, в приведенном выше примере ответ если 5 - 3 = 2.

Я знаю алгоритм O(NlogN), чтобы найти самую длинную возрастающую подпоследовательность (LIS). Но с элементами в массиве, находящемся в [1, N], интересно, есть ли решение для поиска LIS массива O(N)?

Или есть решение O(N), чтобы решить начальную проблему, учитывая, что мы знаем, что элементы от 1 до N?

Answer 1

Что вы ищете, это самая длинная возрастающая последовательность, где разница между любыми двумя последовательными элементами равна 1.

Просто найти самую длинную возрастающую последовательность не хватает, например, с 1 5 3 4 2 длинный вкл след имеет длину 3, но проблема может быть решена только в 3 шагов не 2, насколько я могу судить.

Чтобы найти самый длинный вкл SEQ, где разница в O(N) время 1 и O(N) пространства может быть сделано путем выделения helper массива размера N инициализируется все 0, например. Этот массив будет хранить в позиции i длину самой длинной подпоследовательности до i, и если i еще не было замечен, это будет 0.

Затем вы проходите через несортированный массив, и когда вы найдете элемент x, вы устанавливаете helper[x] = helper[x-1] + 1 и обновляете переменную max.

Наконец, стоимость сортировки input_array.length - max

Пример:

array: 3 1 2 
     0 1 2 3 
helper: 0 0 0 0 
max = 0 

step 1: 
check element at position 1 which is 3. helper[3] = helper[3 - 1] + 1 == 1: 
      0 1 2 3 
helper: 0 0 0 1 
max = 1 

step 2: 
check element at position 2 which is 1. helper[1] = helper[1 - 1] + 1 == 1: 
      0 1 2 3 
helper: 0 1 0 1 
max = 1 

step 3: 
check element at position 3 which is 2. helper[2] = helper[2 - 1] + 1 == 2: 
      0 1 2 3 
helper: 0 1 2 1 
max = 2 

cost = 3 - 2 = 1