Compruebe si una array se puede ordenar eligiendo solo los elementos de la array de esquina

Dada una array arr[] que consta de N elementos, la tarea es verificar si la array dada se puede ordenar seleccionando solo los elementos de las esquinas, es decir, se pueden elegir elementos del lado izquierdo o derecho de la array.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 10, 4, 3, 1} 
Salida: Sí 
Explicación: 
El orden de seleccionar elementos de la array y colocarlos en la array ordenada es el siguiente: 
{2, 3, 4 , 10, 4, 3, 1 } -> {1} 
{ 2 , 3, 4, 10, 4, 3} -> {1, 2} 
{ 3 , 4, 10, 4, 3} -> {1, 2, 3} 
{4, 10, 4, 3 } -> {1, 2, 3, 3} 
{ 4 , 10, 4} -> {1, 2, 3, 3, 4} 
{10, 4 } – > {1, 2, 3, 3, 4, 4} 
{10} -> {1, 2, 3, 3, 4, 4, 10}
Entrada: a[] = {2, 4, 2, 3} 
Salida : No 
 

Enfoque: para resolver el problema, necesitamos usar un concepto similar a la secuencia bitónica. Siga los pasos a continuación para resolver el problema:

• Atraviese la array y verifique si la secuencia de los elementos de la array está disminuyendo, es decir, si el siguiente elemento es más pequeño que el elemento anterior, entonces todos los elementos restantes también deben disminuir o ser iguales.
• Es decir, si la secuencia es no creciente , no decreciente o no decreciente seguida de no creciente , solo entonces la array se puede ordenar según las operaciones dadas.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if an array can
// be sorted using given operations
bool check(int arr[], int n)
{
    int i, g;
    g = 0;
    for (i = 1; i < n; i++) {
 
        // If sequence becomes increasing
        // after an already non-decreasing to
        // non-increasing pattern
        if (arr[i] - arr[i - 1] > 0 && g == 1)
            return false;
 
        // If a decreasing pattern is observed
        if (arr[i] - arr[i - 1] < 0)
            g = 1;
    }
    return true;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 2, 3, 4, 10, 4, 3, 1 };
    int n = sizeof(arr) / sizeof(int);
    if (check(arr, n) == true)
        cout << "Yes"
                "\n";
    else
        cout << "No"
             << "\n";
 
    return 0;
}

// Java program to implement
// the above approach
class GFG{
 
// Function to check if an array can
// be sorted using given operations
static boolean check(int arr[], int n)
{
    int i, g;
    g = 0;
 
    for(i = 1; i < n; i++)
    {
         
        // If sequence becomes increasing
        // after an already non-decreasing to
        // non-increasing pattern
        if (arr[i] - arr[i - 1] > 0 && g == 1)
            return false;
 
        // If a decreasing pattern is observed
        if (arr[i] - arr[i - 1] < 0)
            g = 1;
    }
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 2, 3, 4, 10, 4, 3, 1 };
    int n = arr.length;
     
    if (check(arr, n) == true)
    {
        System.out.println("Yes");
    } else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by rutvik_56

# Python3 program to implement
# the above approach
 
# Function to check if an array can
# be sorted using given operations
def check(arr, n):
 
    g = 0
     
    for i in range(1, n):
 
        # If sequence becomes increasing
        # after an already non-decreasing to
        # non-increasing pattern
        if(arr[i] - arr[i - 1] > 0 and g == 1):
            return False
 
        # If a decreasing pattern is observed
        if(arr[i] - arr[i] < 0):
            g = 1
 
    return True
 
# Driver Code
arr = [ 2, 3, 4, 10, 4, 3, 1 ]
n = len(arr)
 
if(check(arr, n) == True):
    print("Yes")
else:
    print("No")
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to check if an array can
// be sorted using given operations
static bool check(int []arr, int n)
{
    int i, g;
    g = 0;
 
    for(i = 1; i < n; i++)
    {
         
        // If sequence becomes increasing
        // after an already non-decreasing to
        // non-increasing pattern
        if (arr[i] - arr[i - 1] > 0 && g == 1)
            return false;
 
        // If a decreasing pattern is observed
        if (arr[i] - arr[i - 1] < 0)
            g = 1;
    }
    return true;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 2, 3, 4, 10, 4, 3, 1 };
    int n = arr.Length;
     
    if (check(arr, n) == true)
    {
        Console.WriteLine("Yes");
    } else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by sapnasingh4991

<script>
// Javascript Program to implement
// the above approach
 
// Function to check if an array can
// be sorted using given operations
function check(arr, n)
{
    var i, g;
    g = 0;
    for (i = 1; i < n; i++) {
 
        // If sequence becomes increasing
        // after an already non-decreasing to
        // non-increasing pattern
        if (arr[i] - arr[i - 1] > 0 && g == 1)
            return false;
 
        // If a decreasing pattern is observed
        if (arr[i] - arr[i - 1] < 0)
            g = 1;
    }
    return true;
}
 
// Driver Code
var arr = [ 2, 3, 4, 10, 4, 3, 1 ];
var n = arr.length;
if (check(arr, n) == true)
    document.write( "Yes"+
            "<br>");
else
    document.write( "No"
         + "<br>");
 
// This code is contributed by noob2000.
</script>

Yes

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