Given an array arr[] of size N, the task is to find the lexicographically smallest permutation of the given array such that the sum of difference between adjacent elements is maximum.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 5 2 3 4 1
Explanation:
Sum of difference between adjacent elements = (5 – 2) + (2 – 3) + (3 – 4) + (4 – 1) = 4.
{5, 2, 3, 4, 1} is lexicographically the smallest array and 4 is the maximum sum possible.Input: arr[] = {3, 4, 1}
Output: 4 3 1
Explanation:
Sum of the difference between adjacent elements = (4 – 3) + (3 – 1) = 3
{4, 3, 1} is the lexicographically smallest permutation of array elements possible. Maximum sum of adjacent elements possible is 3.
Naive Approach: The simplest approach is to generate all permutations of the given array and find the sum of each permutation while keeping track of the maximum sum obtained. In the end, print the lexicographically smallest permutation with the maximum sum.
Time Complexity: O(N * N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observation:
Let the required permutation of the array be {p1, p2, p3, …, pN – 2, pN – 1, pN}.
Sum of the difference of the adjacent elements, S = (p1-p2) + (p2-p3) +….+ (pN – 2 – pN – 1) + (pN – 1 – pN)
= p1 – pn
In order to maximize S, p1 should be the largest element and pN should be the smallest element in the given array arr[]. To build the lexicographically the smallest permutation, arrange the rest of the elements in increasing order. Follow the steps below to solve the problem:
- Sort the array arr[] in ascending order.
- Swap the first array element i.e., a[0] and the last array element i.e., arr[N – 1].
- After completing the above steps, print the modified array arr[].
Below is the implementation of the above approach:
C++
// 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 maximumvoid 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 Codeint main(){ vector<int> arr = { 1, 2, 3, 4, 5 }; maximumSumPermutation(arr); return 0;} |
Java
// Java program for the above approachimport 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. |
Python3
# 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 maximumdef 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 Codeif __name__ == '__main__': arr = [1, 2, 3, 4, 5]; maximumSumPermutation(arr);# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing 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. |
Javascript
<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 maximumfunction 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 Codevar arr = [ 1, 2, 3, 4, 5 ];maximumSumPermutation(arr);// This code is contributed by 29AjayKumar </script> |
5 2 3 4 1
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
