Verifique si la array se puede dividir en dos subsecuencias fusionando quién hace que la array esté ordenada

Dada una array de enteros A[] de tamaño N , la tarea es verificar si la array se puede dividir en dos subsecuencias, de modo que agregar una de ellas al final de la otra haga que la array se ordene.

Una subsecuencia es una secuencia que se puede obtener de la array eliminando algunos o ningún elemento de ella. Puede o no ser una parte continua de una array.

Ejemplos:

Entrada: arr[] = {1, 4, 5, 2, 3, 4}
Salida: Sí
Explicación:
Primera subsecuencia (P): {1, 2, 3, 4};
Segunda Subsecuencia (Q): {4, 5};
La combinación de ambas subsecuencias da una array ordenada: 
P+Q = {1, 2, 3, 4} + {4, 5} = {1, 2, 3, 4, 4, 5}

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

Enfoque: La idea detrás de la solución del problema es:

Haga una copia de la array y ordene la copia. Encuentre dos subsecuencias crecientes de la array que coincidan con el orden de la copia ordenada. Si los elementos combinados de ambas subsecuencias forman el duplicado de la array ordenada, entonces tales subsecuencias son posibles.

Siga los pasos mencionados a continuación para implementar la idea:

• Cree una array temp[] que almacene todos los elementos de la array de entrada. 
• Ordene la   array   temp[] .
• Iterar dos veces en la array de entrada sin ordenar e intentar encontrar dos subsecuencias ordenadas, que tengan el mismo orden que en la array temp[].
  • Combinar estas dos subsecuencias.
  • Si la array fusionada es un duplicado de la array temp[], se cumple el requisito.
• Si tales subsecuencias no son posibles, devuelva «No» como respuesta.

Siga la siguiente ilustración para una mejor comprensión.

Ilustración:

Considere la array arr[] = {1, 4, 5, 2, 3, 4} ;
Por lo tanto, array temp[] (ordenada por array de entrada): {1, 2, 3, 4, 4, 5} ;

Primera iteración (encontrar la primera subsecuencia ordenada): 
        => Obtendremos los elementos 1, 2, 3 y 4 que mantienen el orden como en temp[], 
        => Almacenarlos en otra array: {1, 2, 3, 4} .  

Segunda iteración (encontrar la segunda subsecuencia ordenada): 
        => Obtendremos 4, 5. 
        => Ahora agregue estos elementos también en la nueva array: {1, 2, 3, 4, 4, 5} .

Se han completado 2 iteraciones. 
temp[] = nueva array

Entonces la salida será «Sí». 

A continuación se muestra la implementación de este enfoque: 

// Java code to implement the approach
  
import java.util.*;
  
class GFG {
    
    // Function to check if two subsequences exist
    public static void solve(int[] arr1)
    {
        // Temprorary array, which will contain 
        // same element and in sorted order 
        // of input array
        int[] temp = new int[arr1.length];
  
        for (int i = 0; i < arr1.length; i++) {
            temp[i] = arr1[i];
        }
        Arrays.sort(temp);
  
        // Counter to iterate on temp[] array 
        // to find elements in sorted manner.
        int counter = 0;
  
        // New array which will store searched elements 
        // in two iterations.
        int[] arr = new int[arr1.length];
  
        // Loop for searching twice in input array.
        for (int i = 0; i < 2; i++) {
  
            // Loop to search for elements in
            // sorted manner in input array.
            for (int j = 0; j < arr1.length; j++) {
  
                // When element at temp[counter] 
                // and arr1[j] matches.
                if (arr1[j] == temp[counter]) {
  
                    // Storing that element in array
                    arr[counter] = arr1[j];
  
                    counter++;
                    if (counter == temp.length) {
                        break;
                    }
                }
            }
        }
        System.out.println(Arrays.equals(arr, temp) == true
                               ? "Yes"
                               : "No");
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 4, 5, 2, 3, 4 };
        
        // Function call
        solve(arr);
    }
}

Yes

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)