Проверить, делает ли удаление подпоследовательности несмежных элементов массив отсортированным

Учитывая двоичный массив arr[] размера N , задача состоит в том, чтобы проверить, можно ли сделать массив arr[] отсортированным, удалив любую подпоследовательность несмежных элементов массива. Если массив можно сделать отсортированным, то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: arr[] = {1, 0, 1, 0, 1, 1, 0}
Output: Yes
Explanation: 
Remove the element at indices {1, 3, 6} modifies the given array to {1, 1, 1, 1}, which is sorted. Therefore, print Yes.

Input: arr[] = {0, 1, 1, 0, 0}
Output: No

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подпоследовательности несмежных элементов, и если существует какая-либо подпоследовательность, удаление которой сортирует данный массив, то выведите «Да» . В противном случае выведите «Нет» .

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

Эффективный подход. Описанный выше подход также можно оптимизировать, основываясь на наблюдении, что массив не может быть отсортирован тогда и только тогда, когда существуют две последовательные единицы , присутствующие в соседних индексах i и i + 1 , и два последовательных нуля в соседних индексах. индексы j и j + 1 такие, что (j > i) . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, idx как -1 , которая хранит индекс, если в массиве есть две последовательные единицы.
• Пройдите по заданному массиву, и если в массиве присутствуют какие-либо две последовательные единицы , сохраните этот индекс в переменной idx и выйдите из цикла. В противном случае удалите все единицы из массива, сделайте массив отсортированным и выведите «Да» .
• Если значение idx равно «-1» , то выведите «Да», поскольку удаление всех единиц из массива всегда делает массив отсортированным.
• В противном случае снова пройдитесь по массиву из индекса idx и, если существуют два последовательных 0 , затем распечатайте и прервите цикл. В противном случае удалите все 0 из массива, отсортируйте массив и выведите «Да» .

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

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