Отсортируйте перестановку от 1 до N, удалив любой элемент и вставив его спереди или сзади

Учитывая массив arr[] размера N , содержащий различные целые числа от 1 до N, задача состоит в том, чтобы подсчитать минимальное количество шагов, необходимых для сортировки массива в порядке возрастания, путем удаления любого элемента и вставки его в начало или конец массива. .

Примеры:

Input: arr[ ] = {4, 1, 3, 2}
Output: 2
Explanation:
The given array can be sorted in increasing order by following two operations:
Operation 1: Remove 3 and add it to the back of the array. {4, 1, 3, 2} -> {4, 1, 2, 3}
Operation 2: Remove 4 and add it to the back of the array. {4, 1, 2, 3} -> {1, 2, 3, 4}

Input: arr[ ] = {4, 1, 2, 5, 3}
Output: 2

Подход: Задачу можно решить, используя тот факт, что для того, чтобы массив отсортировался за минимальное количество шагов, нужно переместить вперед или назад минимальное количество элементов. Также элементы, положение которых необходимо изменить, изначально не будут лежать в порядке возрастания . Таким образом, проблема сводится к поиску самого длинного растущего подмассива, поскольку только те элементы массива не будут перемещены.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)