Maximum sum of absolute differences between distinct pairs of a triplet from an...
source link: https://www.geeksforgeeks.org/maximum-sum-of-absolute-differences-between-distinct-pairs-of-a-triplet-from-an-array/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Maximum sum of absolute differences between distinct pairs of a triplet from an array
- Difficulty Level : Basic
- Last Updated : 06 Apr, 2021
Given an array arr[] consisting of N integers, the task is to find the maximum sum of absolute differences between all distinct pairs of the triplet in the array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 6
Explanation:
The valid triplet is (1, 3, 4) as sum = |1 – 4| + |1 – 3| + |3 – 4| = 6, which is the maximum among all the triplets.Input: arr[] = {2, 2, 2}
Output: 0
Approach: The idea is to solve the given problem is to sort the array in ascending order and find the sum of absolute differences between the pairs of the first and the last two elements of the array. Follow the steps below to solve the problem:
- Initialize a variable, say sum, to store the maximum possible sum.
- Sort the given array arr[] in ascending order.
- Find the sum of differences between the pairs of the first and the last two elements of the array i.e., sum = (arr[N – 2] – arr[0]) + (arr[N – 1] – arr[0]) + (arr[N – 2] – arr[N – 1]).
- After completing the above steps, print the value of the sum as the result.
Below is the implementation of the above approach:
- Python3
- Javascript
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// absolute differences between// distinct pairs of triplet in arrayvoid maximumSum(int arr[], int N){// Stores the maximum sumint sum;// Sort the array in// ascending ordersort(arr, arr + N);// Sum of differences between// pairs of the tripletsum = (arr[N - 1] - arr[0])+ (arr[N - 2] - arr[0])+ (arr[N - 1] - arr[N - 2]);// Print the sumcout << sum;}// Driver Codeint main(){int arr[] = { 1, 3, 4, 2 };int N = sizeof(arr) / sizeof(arr[0]);maximumSum(arr, N);return 0;} |
6
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK