Дан массив целых чисел a[1..n], где все элементы уникальны.После поворота подмассива a[i..j] мы получим новый массив a[1..i-1] a[j,j-1,..i+1,i] a[j+1..n]
Вопрос в том, чтобы найти минимальные шаги поворота для получения увеличивающегося массива [Проблема алгоритма].
Существует ли алгоритм малой сложности для решения этой проблемы?
Пример 1. Для массива 3 2 4 1 для сортировки массива необходимо выполнить два шага.
3 2 [4 1] // rotate subarray [4 1]
-> [3 2 1] 4 // rotate subarray [3 2 1]
-> 1 2 3 4
Пример 2. Для массива 5 4 6 7 3 1 2 необходимо выполнить три шага.
5 4 [6 7 3] 1 2
-> 5 4 3 [7 6 1 2]
-> [5 4 3 2 1] 6 7
-> 1 2 3 4 5 6 7