Maximize difference between the sum of absolute differences of each element with the remaining array
Given an array arr[] consisting of N integers, the task is to maximize the difference between the sum of absolute difference of an element with the remaining elements in the array.
Examples:
Input: arr[] = {1, 2, 4, 7}
Output: 6
Explanation:
For i = 1, |1 β 2| + |1 β 4| + |1 β 7| = 1 + 3 + 6 =10.
For i = 2, |2 β 1| + |2 β 4| + |2 β 7| = 1 + 2 + 5 = 8.
For i = 3, |4 β 1| + |4 β 2| + |4 β 7| = 3 + 2 + 3 = 8.
For i = 4, |7 β 1| + |7 β 2| + |7 β 4| = 6 + 5 + 3 = 14.
Maximum=14, Minimum=8.
Therefore, the maximum difference = 14 β 8 = 6.Input: arr[] = {2, 1, 5, 4, 3}
Output: 4
Naive Approach: The simplest idea is to traverse the array and for each array element, traverse the array using a nested loop and calculate and store the sum of its absolute difference with the remaining array. While calculating, keep track of the maximum and minimum sums obtained. Finally, print the difference between the maximum and minimum sums.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; void findMaxDifference( int arr[], int n) { int Max = INT_MIN; int Min = INT_MAX; // Iterate through all elements of the array for ( int i = 0; i < n; i++) { int sum = 0; // Find the sum of absolute differences // of arr[i] with all other elements for ( int j = 0; j < n; j++) { sum += abs (arr[i] - arr[j]); } // Update the maximum and minimum Max = max(Max, sum); Min = min(Min, sum); } // Print the result cout << Max - Min << endl; } int main() { int arr[] = {1, 2, 4, 7}; int n = sizeof (arr) / sizeof (arr[0]); findMaxDifference(arr, n); return 0; } |
Java
import java.util.*; public class GFG { // Function to find the maximum difference of absolute // differences static void findMaxDifference( int [] arr, int n) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; // Iterate through all elements of the array for ( int i = 0 ; i < n; i++) { int sum = 0 ; // Find the sum of absolute differences of // arr[i] with all other elements for ( int j = 0 ; j < n; j++) { sum += Math.abs(arr[i] - arr[j]); } // Update the maximum and minimum max = Math.max(max, sum); min = Math.min(min, sum); } // Print the result System.out.println(max - min); } public static void main(String[] args) { int [] arr = { 1 , 2 , 4 , 7 }; int n = arr.length; findMaxDifference(arr, n); } } |
Python
def find_max_difference(arr): # Initialize variables to store maximum and minimum values max_val = float ( '-inf' ) min_val = float ( 'inf' ) # Iterate through all elements of the array for i in range ( len (arr)): total_sum = 0 # Find the sum of absolute differences # of arr[i] with all other elements for j in range ( len (arr)): total_sum + = abs (arr[i] - arr[j]) # Update the maximum and minimum values max_val = max (max_val, total_sum) min_val = min (min_val, total_sum) # Print the result (difference between maximum and minimum values) print (max_val - min_val) # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 4 , 7 ] find_max_difference(arr) # sinudp5vi |
C#
using System; class GFG { static void FindMaxDifference( int [] arr, int n) { int max = int .MinValue; int min = int .MaxValue; // Iterate through all elements of the array for ( int i = 0; i < n; i++) { int sum = 0; // Find the sum of absolute differences // of arr[i] with all other elements for ( int j = 0; j < n; j++) { sum += Math.Abs(arr[i] - arr[j]); } // Update the maximum and minimum max = Math.Max(max, sum); min = Math.Min(min, sum); } // Print the result Console.WriteLine(max - min); } static void Main() { int [] arr = { 1, 2, 4, 7 }; int n = arr.Length; FindMaxDifference(arr, n); } } |
Javascript
function findMaxDifference(arr, n) { let Max = Number.MIN_SAFE_INTEGER; let Min = Number.MAX_SAFE_INTEGER; // Iterate through all elements of the array for (let i = 0; i < n; i++) { let sum = 0; // Find the sum of absolute differences // of arr[i] with all other elements for (let j = 0; j < n; j++) { sum += Math.abs(arr[i] - arr[j]); } // Update the maximum and minimum Max = Math.max(Max, sum); Min = Math.min(Min, sum); } // Prlet the result console.log(Max - Min); } let arr = [1, 2, 4, 7]; let n = arr.length; findMaxDifference(arr, n); |
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the observation that in a sorted array, for any index i, the elements on its left will be smaller and elements on its right will be greater. The sum of absolute difference for any element arr[i] in this sorted array can be calculated using the following formula:
(Number of elements to its left)*(arr[i]) β Sum of elements to its left + Sum of elements to its right β (Number of elements to its right)*(arr[i]))
Follow the steps below to solve the problem:
- Initialize totalSum as 0 to store the sum of all the element of the array and leftSum as 0 to store the sum of elements on the left of any index.
- Initialize two variables, Max as INT_MIN and Min as INT_MAX.
- Sort the array arr[] in ascending order.
- Traverse the array, arr[] using the variable i and do the following:
- Store the sum of absolute difference of arr[i] with the rest of the elements using the formula in Sum = (i * arr[i]) β leftSum + totalSum β ((N β i β 1) * arr[i]).
- Update Max to the maximum of Max and Sum.
- Update Min to the minimum of Min and Sum.
- After the above steps, print the value of Max and Min as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to maximize difference of // the sum of absolute difference of // an element with the rest of the // elements in the array void findMaxDifference( int arr[], int n) { // Sort the array in ascending order sort(arr, arr + n); // Stores prefix sum at any instant int Leftsum = 0; // Store the total array sum int Totalsum = 0; // Initialize minimum and maximum // absolute difference int Min = INT_MAX, Max = INT_MIN; // Traverse the array to find // the total array sum for ( int i = 0; i < n; i++) Totalsum += arr[i]; // Traverse the array arr[] for ( int i = 0; i < n; i++) { // Store the number of // elements to its left int leftNumbers = i; // Store the number of // elements to its right int rightNumbers = n - i - 1; // Update the sum of elements // on its left Totalsum = Totalsum - arr[i]; // Store the absolute difference sum int sum = (leftNumbers * arr[i]) - Leftsum + Totalsum - (rightNumbers * arr[i]); // Update the Minimum Min = min(Min, sum); // Update the Maximum Max = max(Max, sum); // Update sum of elements // on its left Leftsum += arr[i]; } // Print the result cout << Max - Min; } // Driven Code int main() { int arr[] = { 1, 2, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); findMaxDifference(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to maximize difference of // the sum of absolute difference of // an element with the rest of the // elements in the array static void findMaxDifference( int arr[], int n) { // Sort the array in ascending order Arrays.sort(arr); // Stores prefix sum at any instant int Leftsum = 0 ; // Store the total array sum int Totalsum = 0 ; // Initialize minimum and maximum // absolute difference int Min = Integer.MAX_VALUE, Max = Integer.MIN_VALUE; // Traverse the array to find // the total array sum for ( int i = 0 ; i < n; i++) Totalsum += arr[i]; // Traverse the array arr[] for ( int i = 0 ; i < n; i++) { // Store the number of // elements to its left int leftNumbers = i; // Store the number of // elements to its right int rightNumbers = n - i - 1 ; // Update the sum of elements // on its left Totalsum = Totalsum - arr[i]; // Store the absolute difference sum int sum = (leftNumbers * arr[i]) - Leftsum + Totalsum - (rightNumbers * arr[i]); // Update the Minimum Min = Math.min(Min, sum); // Update the Maximum Max = Math.max(Max, sum); // Update sum of elements // on its left Leftsum += arr[i]; } // Print the result System.out.print(Max - Min); } // Driven Code public static void main(String[] args) { int arr[] = { 1 , 2 , 4 , 7 }; int N = arr.length; findMaxDifference(arr, N); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to maximize difference of # the sum of absolute difference of # an element with the rest of the # elements in the array def findMaxDifference(arr, n): # Sort the array in ascending order arr = sorted (arr) # Stores prefix sum at any instant Leftsum = 0 # Store the total array sum Totalsum = 0 # Initialize minimum and maximum # absolute difference Min , Max = 10 * * 8 , - 10 * * 8 # Traverse the array to find # the total array sum for i in range (n): Totalsum + = arr[i] # Traverse the array arr[] for i in range (n): # Store the number of # elements to its left leftNumbers = i # Store the number of # elements to its right rightNumbers = n - i - 1 # Update the sum of elements # on its left Totalsum = Totalsum - arr[i] # Store the absolute difference sum sum = (leftNumbers * arr[i]) - Leftsum + Totalsum - (rightNumbers * arr[i]) # Update the Minimum Min = min ( Min , sum ) # Update the Maximum Max = max ( Max , sum ) # Update sum of elements # on its left Leftsum + = arr[i] # Prthe result print ( Max - Min ) # Driven Code if __name__ = = '__main__' : arr = [ 1 , 2 , 4 , 7 ] N = len (arr) findMaxDifference(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# Program to implement // the above approach using System; class GFG { // Function to maximize difference of // the sum of absolute difference of // an element with the rest of the // elements in the array static void findMaxDifference( int [] arr, int n) { // Sort the array in ascending order Array.Sort(arr); // Stores prefix sum at any instant int Leftsum = 0; // Store the total array sum int Totalsum = 0; // Initialize minimum and maximum // absolute difference int Minn = Int32.MaxValue, Maxx = Int32.MinValue; // Traverse the array to find // the total array sum for ( int i = 0; i < n; i++) Totalsum += arr[i]; // Traverse the array arr[] for ( int i = 0; i < n; i++) { // Store the number of // elements to its left int leftNumbers = i; // Store the number of // elements to its right int rightNumbers = n - i - 1; // Update the sum of elements // on its left Totalsum = Totalsum - arr[i]; // Store the absolute difference sum int sum = (leftNumbers * arr[i]) - Leftsum + Totalsum - (rightNumbers * arr[i]); // Update the Minimum Minn = Math.Min(Minn, sum); // Update the Maximum Maxx = Math.Max(Maxx, sum); // Update sum of elements // on its left Leftsum += arr[i]; } // Print the result Console.WriteLine(Maxx - Minn); } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 2, 4, 7 }; int N = arr.Length; findMaxDifference(arr, N); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // javascript program of the above approach // Function to maximize difference of // the sum of absolute difference of // an element with the rest of the // elements in the array function findMaxDifference(arr, n) { // Sort the array in ascending order arr.sort(); // Stores prefix sum at any instant let Leftsum = 0; // Store the total array sum let Totalsum = 0; // Initialize minimum and maximum // absolute difference let Min = Number.MAX_VALUE, Max = Number.MIN_VALUE; // Traverse the array to find // the total array sum for (let i = 0; i < n; i++) Totalsum += arr[i]; // Traverse the array arr[] for (let i = 0; i < n; i++) { // Store the number of // elements to its left let leftNumbers = i; // Store the number of // elements to its right let rightNumbers = n - i - 1; // Update the sum of elements // on its left Totalsum = Totalsum - arr[i]; // Store the absolute difference sum let sum = (leftNumbers * arr[i]) - Leftsum + Totalsum - (rightNumbers * arr[i]); // Update the Minimum Min = Math.min(Min, sum); // Update the Maximum Max = Math.max(Max, sum); // Update sum of elements // on its left Leftsum += arr[i]; } // Prlet the result document.write(Max - Min); } // Driver Code // Given array let arr = [ 1, 2, 4, 7 ]; let N = arr.length; findMaxDifference(arr, N); // This code is contributed by target_2. </script> |
6
Time Complexity: O(N*log N)
Auxiliary Space: O(1)