Dada una array arr[] de tamaño N, la tarea es encontrar la array de permutación lexicográficamente más grande invirtiendo cualquier sufijo de la array.
Ejemplos:
Entrada: arr[] = {3, 5, 4, 1, 2}
Salida: 3 5 4 2 1
Explicación: Invertir el sufijo subarreglo {1, 2} genera la permutación lexicográficamente más grande posible de los elementos del arreglo.Entrada: arr[] = {3, 5, 1, 2, 1}
Salida: 3 5 1 2 1
Explicación:
La array dada arr[] ya es la permutación lexicográficamente más grande posible de la array.
Enfoque ingenuo: el enfoque más simple es invertir todos los sufijos posibles de la array e imprimir la permutación de los elementos de la array que sea lexicográficamente lo más grande posible.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el enfoque codicioso . El problema planteado se puede resolver con base en las siguientes observaciones:
Se puede observar que eligiendo el arreglo de sufijos como subarreglo en el rango [i, N – 1] tal que arr[i] < arr[N – 1] e invirtiéndolo, el arreglo obtenido será lexicográficamente el arreglo más grande.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos marcar como -1 , que representa un índice que tiene un valor menor que el último elemento.
- Recorra la array dada arr[] y en cada iteración, verifique si arr[i] < arr[N – 1] o no. Luego, almacene el índice actual en el indicador de variable y rompa el ciclo .
- Después de completar los pasos anteriores, verifique si el valor de la bandera es -1 o no. Si se determina que es cierto, invierta el sufijo subarreglo, es decir, subarreglo en el rango [bandera, N – 1] .
- Después de completar los pasos anteriores, imprima la array arr[] como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; // Function that void LLA(vector<int> A) { // Stores the index that have // element less than the // element at last index int flg = -1; // Traverse the array for (int i = 0; i < A.size(); i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.size() - 1]) { // Assign the current // index value to index flg = i; break; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for (int i = flg, j = A.size() - 1; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for (int i = 0; i < A.size(); i++) cout<<A[i]<<" "; } // Driver Code int main() { vector<int> arr= { 3, 5, 4, 1, 2 }; // Function Call LLA(arr); } // This code is contributed by mohit kumar 29.
Java
// Java program for the above approach import java.io.*; class GFG { // Function that public static void LLA(int A[]) { // Stores the index that have // element less than the // element at last index int flg = -1; // Traverse the array for (int i = 0; i < A.length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.length - 1]) { // Assign the current // index value to index flg = i; break; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for (int i = flg, j = A.length - 1; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for (int i = 0; i < A.length; i++) System.out.print(A[i] + " "); } // Driver Code public static void main(String[] args) { int arr[] = { 3, 5, 4, 1, 2 }; // Function Call LLA(arr); } }
Python3
# Python program for the above approach # Function that def LLA(A): # Stores the index that have # element less than the # element at last index flg = -1; # Traverse the array for i in range(len(A)): # Checks if value at the # current index is less # than value at last index if (A[i] < A[len(A) - 1]): # Assign the current # index value to index flg = i; break; # Check if index is not -1 then # reverse the suffix from the # index stored at flg if (flg != -1): # Reversal of suffix j = len(A) - 1; for i in range(flg, j + 1): # Swapping Step temp = A[i]; A[i] = A[j]; A[j] = temp; j -= 1; # Print the final Array for i in range(len(A)): print(A[i], end=" "); # Driver Code if __name__ == '__main__': arr = [3, 5, 4, 1, 2]; # Function Call LLA(arr); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach using System; public class GFG { // Function that public static void LLA(int []A) { // Stores the index that have // element less than the // element at last index int flg = -1; // Traverse the array for (int i = 0; i < A.Length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.Length - 1]) { // Assign the current // index value to index flg = i; break; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for (int i = flg, j = A.Length - 1; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the readonly Array for (int i = 0; i < A.Length; i++) Console.Write(A[i] + " "); } // Driver Code public static void Main(String[] args) { int []arr = { 3, 5, 4, 1, 2 }; // Function Call LLA(arr); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program for the above approach // Function that function LLA(A) { // Stores the index that have // element less than the // element at last index var flg = -1; var i,j; // Traverse the array for (i = 0; i < A.length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.length - 1]) { // Assign the current // index value to index flg = i; break; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for (i = flg, j = A.length - 1; i <= j; i++, j--) { // Swapping Step var temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for (i = 0; i < A.length; i++) document.write(A[i] + " "); } // Driver Code var arr = [3, 5, 4, 1, 2]; // Function Call LLA(arr); </script>
3 5 4 2 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)