Разбить заданный массив на минимальное количество подмассивов так, чтобы изменение порядка подмассивов сортировало массив

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

Примеры:

Input: arr[] = {6, 3, 4, 2, 1}
Output: 4
Explanation:
The given array can be divided into 4 subarrays as {6}, {3, 4}, {2}, {1} and these subarrays can be rearranged as {1}, {2}, {3, 4}, {6}. The resulting array will be {1, 2, 3, 4, 6} which is sorted. So, the minimum subarrays the given array can be divided to sort the array is 4.

Input: arr[] = {1, -4, 0, -2}
Output: 4

Подход: Данную проблему можно решить, поддерживая отсортированную версию массива arr[] и группируя вместе все целые числа в исходном массиве, которые появляются в той же последовательности, что и в отсортированном массиве. Ниже приведены шаги:

• Поддерживать вектор пары V , который хранит значение текущего элемента и индекс текущего элемента массива arr[] для всех элементов в данном массиве.
• Отсортируйте вектор V .
• Инициализируйте переменную, скажем, cnt как 1 , которая хранит минимальное количество требуемых подмассивов.
• Пройдите вектор V для i в диапазоне [1, N – 1] и выполните следующие шаги:
  • Если индекс i ^-го элемента в исходном массиве равен (1 + индекс (i – 1) ^-го элемента) в исходном массиве, то их можно сгруппировать вместе в одном подмассиве.
  • В противном случае два элемента должны находиться в отдельных подмассивах и увеличивать значение cnt на 1 .
• После выполнения вышеуказанных шагов выведите значение cnt как результат возможного разбиения подмассивов.

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

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