Compruebe si la secuencia de elementos intermedios eliminados de una array está ordenada o no

Dada una array arr[] que consta de N enteros, la tarea es verificar si la secuencia de números formada al eliminar repetidamente los elementos intermedios de la array dada arr[] está ordenada o no. Si hay dos elementos intermedios , elimine cualquiera de ellos.

Ejemplos:

Entrada: arr[] = {4, 3, 1, 2, 5}
Salida: Sí
Explicación:
El orden de eliminación de los elementos es: 
Elemento central de la array = arr[2]. Eliminar arr[2] modifica la array a {4, 3, 2, 5}. 
Los elementos intermedios de la array son arr[1] y arr[2]. Eliminar arr[2] modifica la array a {4, 3, 5}. 
El elemento medio de la array es arr[1]. Eliminar arr[1] modifica la array a {4, 5}. 
De manera similar, arr[0] y arr[1] se eliminan de la array. 
Finalmente, la secuencia de elementos de array eliminados es {1, 2, 3, 4, 5}, que se ordena.

Entrada: arr[] = {5, 4, 1, 2, 3}
Salida: No

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es usar la recursividad para generar todas las combinaciones posibles de eliminación de elementos de array. Para las instancias que tienen dos elementos intermedios, se requieren dos llamadas recursivas, una considerando el elemento N/ ^2th y la otra considerando el (N/2 + 1) ^th elemento . Después de completar la recursión, verifique si la array formada por cualquiera de las llamadas recursivas está ordenada o no. Si se encuentra que es cierto, escriba » Sí «. De lo contrario, escriba “No” . 

Complejidad temporal: O(N*2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que los elementos al final de la array deben ser mayores que todos los elementos de la array para obtener una array cada vez más ordenada. 
Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , con “Sí” , para verificar si la secuencia requerida se puede ordenar o no.
• Inicialice dos punteros , digamos L como 0 y R como (N – 1) , para almacenar los índices inicial y final de la array.
• Iterar hasta que L sea menor que R y realizar los siguientes pasos:
  • Si el valor de arr[L] es mayor o igual que el máximo de arr[L + 1] y arr[R – 1] y el valor de arr[R] es mayor o igual que el mínimo de arr[L + 1] y arr[R – 1] , luego incremente el valor de L en 1 y disminuya el valor de R en 1 .
  • De lo contrario, actualice el valor de ans a «No» y salga del bucle .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if sequence of
// removed middle elements from an
// array is sorted or not
bool isSortedArray(int arr[], int n)
{
    // Points to the ends
    // of the array
    int l = 0, r = (n - 1);
 
    // Iterate l + 1 < r
    while ((l + 1) < r) {
 
        // If the element at index L and
        // R is greater than (L + 1)-th
        // and (R - 1)-th elements
        if (arr[l] >= max(arr[l + 1],
                          arr[r - 1])
            && arr[r] >= max(arr[r - 1],
                             arr[l + 1])) {
 
            // If true, then decrement R
            // by 1 and increment L by 1
            l++;
            r--;
        }
 
        // Otherwise, return false
        else {
            return false;
        }
    }
 
    // If an increasing sequence is
    // formed, then return true
    return true;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 3, 1, 2, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    if (isSortedArray(arr, N))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function to check if sequence of
// removed middle elements from an
// array is sorted or not
static boolean isSortedArray(int []arr, int n)
{
     
    // Points to the ends
    // of the array
    int l = 0, r = (n - 1);
 
    // Iterate l + 1 < r
    while ((l + 1) < r)
    {
         
        // If the element at index L and
        // R is greater than (L + 1)-th
        // and (R - 1)-th elements
        if (arr[l] >= Math.max(arr[l + 1],
                               arr[r - 1]) &&
            arr[r] >= Math.max(arr[r - 1],
                               arr[l + 1]))
        {
             
            // If true, then decrement R
            // by 1 and increment L by 1
            l++;
            r--;
        }
 
        // Otherwise, return false
        else
        {
            return false;
        }
    }
 
    // If an increasing sequence is
    // formed, then return true
    return true;
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 4, 3, 1, 2, 5 };
    int N = arr.length;
 
    if (isSortedArray(arr, N))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by bgangwar59

# Python3 program for the above approach
 
# Function to check if sequence of
# removed middle elements from an
# array is sorted or not
def isSortedArray(arr, n):
 
    # Points toa the ends
    # of the array
    l = 0
    r = (n - 1)
 
    # Iterate l + 1 < r
    while ((l + 1) < r):
 
        # If the element at index L and
        # R is greater than (L + 1)-th
        # and (R - 1)-th elements
        if (arr[l] >= max(arr[l + 1],
                          arr[r - 1])
            and arr[r] >= max(arr[r - 1],
                              arr[l + 1])):
 
            # If true, then decrement R
            # by 1 and increment L by 1
            l += 1
            r -= 1
 
        # Otherwise, return false
        else:
            return False
 
    # If an increasing sequence is
    # formed, then return true
    return True
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 4, 3, 1, 2, 5 ]
    N = len(arr)
 
    if (isSortedArray(arr, N)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by ukasp

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if sequence of removed
// middle elements from an array is sorted or not
static bool isSortedArray(int []arr, int n)
{
     
    // Points to the ends
    // of the array
    int l = 0, r = (n - 1);
 
    // Iterate l + 1 < r
    while ((l + 1) < r)
    {
         
        // If the element at index L and
        // R is greater than (L + 1)-th
        // and (R - 1)-th elements
        if (arr[l] >= Math.Max(arr[l + 1],
                               arr[r - 1]) &&
            arr[r] >= Math.Max(arr[r - 1],
                               arr[l + 1]))
        {
             
            // If true, then decrement R
            // by 1 and increment L by 1
            l++;
            r--;
        }
 
        // Otherwise, return false
        else
        {
            return false;
        }
    }
 
    // If an increasing sequence is
    // formed, then return true
    return true;
}
 
// Driver Code
public static void Main(string[] args)
{
    int []arr = { 4, 3, 1, 2, 5 };
    int N = arr.Length;
 
    if (isSortedArray(arr, N))
       Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by sanjoy_62

// JavaScript program for the above approach
 
// Function to check if sequence of
// removed middle elements from an
// array is sorted or not
function isSortedArray(arr, n){
 
    // Points toa the ends
    // of the array
    var l = 0
    var r = (n - 1)
 
    // Iterate l + 1 < r
    while ((l + 1) < r) {
 
        // If the element at index L and
        // R is greater than (L + 1)-th
        // and (R - 1)-th elements
        if (arr[l] >= Math.max(arr[l + 1],
                          arr[r - 1])
            && arr[r] >= Math.max(arr[r - 1],
            arr[l + 1])){
 
            // If true, then decrement R
            // by 1 and increment L by 1
            l += 1
            r -= 1
    }
 
        // Otherwise, return false
        else
            return false
    }
 
    // If an increasing sequence is
    // formed, then return true
    return true
}
 
// Driver Code
 
var arr = [ 4, 3, 1, 2, 5 ]
var N = arr.length
 
if (isSortedArray(arr, N))
      console.log("Yes")
else
      console.log("No")
 
// This code is contributed by AnkThon

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(1)