Verifique si un gráfico construido a partir de una array basada en condiciones dadas consiste en un ciclo o no

Dada una array arr[] que consta de los primeros N números naturales, construya un gráfico no dirigido usando los elementos de la array de tal manera que para cualquier elemento de la array, conecte un borde con el siguiente elemento mayor a la izquierda y a la derecha.

Ejemplos:

 Entrada: arr = {1, 2, 3, 4, 5}
Salida: No
Explicación:     
Está claro en la imagen de abajo que el gráfico final será un árbol. 

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

Enfoque ingenuo: el enfoque más simple es construir el gráfico requerido utilizando las condiciones anteriores y verificar si existe algún ciclo de al menos una longitud de 3 o no. Si existe un ciclo, entonces imprima » Sí «. De lo contrario, escriba “ No ”. 
Complejidad temporal: O(N + E), donde E es el número de aristas.
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea óptima es verificar si la permutación dada es unimodal o no unimodal , es decir, simplemente verificar si existe algún elemento de array con elementos adyacentes mayores en ambos lados. Si es cierto, escriba «Sí». De lo contrario, escriba “No”.
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 the graph
// constructed from given array
// contains a cycle or not
void isCycleExists(int arr[], int N)
{
    bool valley = 0;
 
    // Traverse the array
    for (int i = 1; i < N; i++) {
 
        // If arr[i] is less than
        // arr[i - 1] and arr[i]
        if (arr[i] < arr[i - 1]
            && arr[i] < arr[i + 1]) {
 
            cout << "Yes" << endl;
            return;
        }
    }
 
    cout << "No";
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 3, 2, 4, 5 };
 
    // Size of the array
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    isCycleExists(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to check if the graph
  // constructed from given array
  // contains a cycle or not
  static void isCycleExists(int[] arr, int N)
  {
 
    // Traverse the array
    for (int i = 1; i < N; i++)
    {
 
      // If arr[i] is less than
      // arr[i - 1] and arr[i]
      if (arr[i] < arr[i - 1]
          && arr[i] < arr[i + 1])
      {
        System.out.println("Yes");
        return;
      }
    }
    System.out.println("No");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given array
    int[] arr = { 1, 3, 2, 4, 5 };
 
    // Size of the array
    int N = arr.length;
    isCycleExists(arr, N);
  }
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
 
# Function to check if the graph
# constructed from given array
# contains a cycle or not
def isCycleExists(arr, N):
    valley = 0
 
    # Traverse the array
    for i in range(1, N):
 
        # If arr[i] is less than
        # arr[i - 1] and arr[i]
        if (arr[i] < arr[i - 1] and arr[i] < arr[i + 1]):
            print("Yes")
            return
    print("No")
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [1, 3, 2, 4, 5]
 
    # Size of the array
    N = len(arr)
    isCycleExists(arr, N)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG
{
 
  // Function to check if the graph
  // constructed from given array
  // contains a cycle or not
  static void isCycleExists(int[] arr, int N)
  {
 
    // Traverse the array
    for (int i = 1; i < N; i++)
    {
 
      // If arr[i] is less than
      // arr[i - 1] and arr[i]
      if (arr[i] < arr[i - 1]
          && arr[i] < arr[i + 1])
      {
        Console.WriteLine("Yes");
        return;
      }
    }
    Console.WriteLine("No");
  }
 
  // Driver Code
  public static void Main()
  {
     
    // Given array
    int[] arr = { 1, 3, 2, 4, 5 };
 
    // Size of the array
    int N = arr.Length;
    isCycleExists(arr, N);
  }
}
 
// This code is contributed by chitranayal.

<script>
// Javascript program for the above approach
 
// Function to check if the graph
// constructed from given array
// contains a cycle or not
function isCycleExists(arr,N)
{
    // Traverse the array
    for (let i = 1; i < N; i++)
    {
  
      // If arr[i] is less than
      // arr[i - 1] and arr[i]
      if (arr[i] < arr[i - 1]
          && arr[i] < arr[i + 1])
      {
        document.write("Yes");
        return;
      }
    }
    document.write("No");
}
 
// Driver Code
let arr=[1, 3, 2, 4, 5 ];
// Size of the array
let N = arr.length;
isCycleExists(arr, N);
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Yes

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