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)