Permutación lexicográficamente más pequeña que tiene la suma máxima de diferencias entre elementos adyacentes

Dada una array arr[] de tamaño N , la tarea es encontrar la permutación lexicográficamente más pequeña de la array dada de modo que la suma de la diferencia entre elementos adyacentes sea máxima.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 5 2 3 4 1
Explicación:
Suma de la diferencia entre elementos adyacentes = (5 – 2) + (2 – 3) + (3 – 4) + (4 – 1) = 4.
{5, 2, 3, 4, 1} es lexicográficamente la array más pequeña y 4 es la suma máxima posible.

Entrada: arr[] = {3, 4, 1}
Salida: 4 3 1
Explicación:
Suma de la diferencia entre elementos adyacentes = (4 – 3) + (3 – 1) = 3
{4, 3, 1} es la permutación lexicográficamente más pequeña posible de los elementos de la array. La suma máxima posible de elementos adyacentes es 3.

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones de la array dada y encontrar la suma de cada permutación mientras se realiza un seguimiento de la suma máxima obtenida. Al final, imprima la permutación lexicográficamente más pequeña con la suma máxima. 

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

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la siguiente observación:

Sea la permutación requerida del arreglo {p ₁ , p ₂ , p ₃ , …, p _{N – 2} , p _{N – 1,} p _N }. 
Suma de la diferencia de los elementos adyacentes, S = (p ₁ -p ₂ ) + (p ₂ -p ₃ ) +….+ (p _{N – 2} – p _{N – 1} ) + (p _{N – 1} – p _N )
                                                                             = pag ₁ – pag _norte

Para maximizar S , p ₁ debe ser el elemento más grande y p _N debe ser el elemento más pequeño en la array dada arr[] . Para construir lexicográficamente la permutación más pequeña, ordene el resto de los elementos en orden creciente. Siga los pasos a continuación para resolver el problema:

• Ordene la array arr[] en orden ascendente.
• Intercambie el primer elemento de la array, es decir, a[0], y el último elemento de la array, es decir, arr[N – 1] .
• Después de completar los pasos anteriores, imprima la array modificada arr[] .

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 find the lexicographically
// smallest permutation of an array such
// that the sum of the difference between
// adjacent elements is maximum
void maximumSumPermutation(vector<int>& arr)
{
 
    // Stores the size of the array
    int N = arr.size();
 
    // Sort the given array in
    // increasing order
    sort(arr.begin(), arr.end());
 
    // Swap the first and last array elements
    swap(arr[0], arr[N - 1]);
 
    // Print the required permutation
    for (int i : arr) {
 
        cout << i << " ";
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    maximumSumPermutation(arr);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
    // Function to find the lexicographically
    // smallest permutation of an array such
    // that the sum of the difference between
    // adjacent elements is maximum
    static void maximumSumPermutation(int[] arr)
    {
 
        // Stores the size of the array
        int N = arr.length;
 
        // Sort the given array in
        // increasing order
        Arrays.sort(arr);
 
        // Swap the first and last array elements
          int temp = arr[0];
          arr[0] = arr[N - 1];
        arr[N - 1] = temp;
 
        // Print the required permutation
        for (int i : arr) {
 
            System.out.print(i + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        maximumSumPermutation(arr);
    }
}
 
// This code is contributed by Dharanendra L V.

# Python program for the above approach
 
# Function to find the lexicographically
# smallest permutation of an array such
# that the sum of the difference between
# adjacent elements is maximum
def maximumSumPermutation(arr):
   
    # Stores the size of the array
    N = len(arr);
 
    # Sort the given array in
    # increasing order
    arr.sort();
 
    # Swap the first and last array elements
    temp = arr[0];
    arr[0] = arr[N - 1];
    arr[N - 1] = temp;
 
    # Print the required permutation
    for i in arr:
        print(i, end = " ");
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5];
    maximumSumPermutation(arr);
 
# This code is contributed by 29AjayKumar

// C# program to implement
// the above approach
using System;
class GFG{
 
  // Function to find the lexicographically
  // smallest permutation of an array such
  // that the sum of the difference between
  // adjacent elements is maximum
  static void maximumSumPermutation(int[] arr)
  {
 
    // Stores the size of the array
    int N = arr.Length;
 
    // Sort the given array in
    // increasing order
    Array.Sort(arr);
 
    // Swap the first and last array elements
    int temp = arr[0];
    arr[0] = arr[N - 1];
    arr[N - 1] = temp;
 
    // Print the required permutation
    foreach (int i in arr)
    {
      Console.Write(i + " ");
    }
  }
 
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4, 5 };
    maximumSumPermutation(arr);
  }
}
 
// This code is contributed by sanjoy_62.

<script>
// javascript program for the above approach
 
// Function to find the lexicographically
// smallest permutation of an array such
// that the sum of the difference between
// adjacent elements is maximum
function maximumSumPermutation(arr)
{
 
    // Stores the size of the array
    var N = arr.length;
    // Sort the given array in
    // increasing order
    arr.sort((a,b)=>a-b);
    // Swap the first and last array elements
      var temp = arr[0];
      arr[0] = arr[N - 1];
      arr[N - 1] = temp;
 
    // Print the required permutation
    document.write(arr);
}
 
// Driver Code
var arr = [ 1, 2, 3, 4, 5 ];
maximumSumPermutation(arr);
 
// This code is contributed by 29AjayKumar
</script>

5 2 3 4 1

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