Given an array arr[] consisting of N integers, the task is to find the absolute difference between the minimum and maximum sum of any pairs of elements (arr[i], arr[j]) such that (i < j) and (arr[i] < arr[j]).
Examples:
Input: arr[] = {1, 2, 4, 7}
Output: 8
Explanation: All possible pairs are:
- (1, 2) ? Sum = 3
- (1, 4) ? Sum = 5
- (1, 7) ? Sum = 8
- (2, 4) ? Sum = 6
- (2, 7) ? Sum = 9
- (4, 7) ? Sum = 11
Therefore, the difference between maximum and minimum sum = 11 – 3 = 8.
Input: arr[] = {2, 5, 3}
Output: 2
Approach: The idea to solve the given problem is to create two auxiliary arrays to store minimum and maximum of suffixes of every index of suffixes of the given array and then find the required absolute difference.
Follow the steps below to solve the problem:
- Initialize two variables, say maxSum and minSum, to store the maximum and minimum sum of a pair of elements from the given array according to the given conditions.
- Initialize two arrays, say suffixMax[] and suffixMin[] of size N, to store the maximum and minimum of suffixes for each index of the array arr[].
- Traverse the given array arr[] in reverse and update suffixMin[] and suffixMax[] at each index.
- Now, iterate over the range [0, N – 1] and perform the following steps:
- If the current element arr[i] is less than suffixMax[i], then update the value of maxSum as the maximum of maxSum and (arr[i] + suffixMax[i]).
- If the current element arr[i] is less than suffixMin[i], then update the value of minSum as the minimum of minSum and (arr[i] + suffixMin[i]).
- After completing the above steps, print the value (maxSum – minSum) as the resultant difference.
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 difference between// the maximum and minimum sum of a pair// (arr[i], arr[j]) from the array such// that i < j and arr[i] < arr[j]int GetDiff(int A[], int N){ // Stores the maximum from // the suffix of the array int SuffMaxArr[N]; // Set the last element SuffMaxArr[N - 1] = A[N - 1]; // Traverse the remaining array for (int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMaxArr[i] = max(SuffMaxArr[i + 1], A[i + 1]); } // Stores the maximum sum of any pair int MaximumSum = INT_MIN; // Calculate the maximum sum for (int i = 0; i < N - 1; i++) { if (A[i] < SuffMaxArr[i]) MaximumSum = max(MaximumSum, A[i] + SuffMaxArr[i]); } // Stores the maximum sum of any pair int MinimumSum = INT_MAX; // Stores the minimum of suffixes // from the given array int SuffMinArr[N]; // Set the last element SuffMinArr[N - 1] = INT_MAX; // Traverse the remaining array for (int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMinArr[i] = min(SuffMinArr[i + 1], A[i + 1]); } // Calculate the minimum sum for (int i = 0; i < N - 1; i++) { if (A[i] < SuffMinArr[i]) { MinimumSum = min(MinimumSum, A[i] + SuffMinArr[i]); } } // Return the resultant difference return abs(MaximumSum - MinimumSum);}// Driver Codeint main(){ int arr[] = { 2, 4, 1, 3, 7, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << GetDiff(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find the difference between// the maximum and minimum sum of a pair// (arr[i], arr[j]) from the array such// that i < j and arr[i] < arr[j]static int GetDiff(int A[], int N){ // Stores the maximum from // the suffix of the array int SuffMaxArr[] = new int[N]; // Set the last element SuffMaxArr[N - 1] = A[N - 1]; // Traverse the remaining array for(int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMaxArr[i] = Math.max(SuffMaxArr[i + 1], A[i + 1]); } // Stores the maximum sum of any pair int MaximumSum = Integer.MIN_VALUE; // Calculate the maximum sum for(int i = 0; i < N - 1; i++) { if (A[i] < SuffMaxArr[i]) MaximumSum = Math.max(MaximumSum, A[i] + SuffMaxArr[i]); } // Stores the maximum sum of any pair int MinimumSum = Integer.MAX_VALUE; // Stores the minimum of suffixes // from the given array int SuffMinArr[] = new int[N]; // Set the last element SuffMinArr[N - 1] = Integer.MAX_VALUE; // Traverse the remaining array for(int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMinArr[i] = Math.min(SuffMinArr[i + 1], A[i + 1]); } // Calculate the minimum sum for(int i = 0; i < N - 1; i++) { if (A[i] < SuffMinArr[i]) { MinimumSum = Math.min(MinimumSum, A[i] + SuffMinArr[i]); } } // Return the resultant difference return Math.abs(MaximumSum - MinimumSum);}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 4, 1, 3, 7, 5, 6 }; int N = arr.length; // Function Call System.out.println(GetDiff(arr, N));}}// This code is contributed by Kingash |
Python3
# Python 3 program for the above approachimport sys# Function to find the difference between# the maximum and minimum sum of a pair# (arr[i], arr[j]) from the array such# that i < j and arr[i] < arr[j]def GetDiff(A, N): # Stores the maximum from # the suffix of the array SuffMaxArr = [0 for i in range(N)] # Set the last element SuffMaxArr[N - 1] = A[N - 1] # Traverse the remaining array i = N-2 while(i >= 0): # Update the maximum from suffix # for the remaining indices SuffMaxArr[i] = max(SuffMaxArr[i + 1], A[i + 1]) i -= 1 # Stores the maximum sum of any pair MaximumSum = -sys.maxsize-1 # Calculate the maximum sum for i in range(N-1): if (A[i] < SuffMaxArr[i]): MaximumSum = max(MaximumSum, A[i] + SuffMaxArr[i]) # Stores the maximum sum of any pair MinimumSum = sys.maxsize # Stores the minimum of suffixes # from the given array SuffMinArr = [0 for i in range(N)] # Set the last element SuffMinArr[N - 1] = sys.maxsize # Traverse the remaining array i = N-2 while(i >= 0): # Update the maximum from suffix # for the remaining indices SuffMinArr[i] = min(SuffMinArr[i + 1], A[i + 1]) i -= 1 # Calculate the minimum sum for i in range(N - 1): if (A[i] < SuffMinArr[i]): MinimumSum = min(MinimumSum,A[i] + SuffMinArr[i]) # Return the resultant difference return abs(MaximumSum - MinimumSum)# Driver Codeif __name__ == '__main__': arr = [2, 4, 1, 3, 7, 5, 6] N = len(arr) # Function Call print(GetDiff(arr, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# Program to implement// the above approachusing System;class GFG {// Function to find the difference between// the maximum and minimum sum of a pair// (arr[i], arr[j]) from the array such// that i < j and arr[i] < arr[j]static int GetDiff(int[] A, int N){ // Stores the maximum from // the suffix of the array int[] SuffMaxArr = new int[N]; // Set the last element SuffMaxArr[N - 1] = A[N - 1]; // Traverse the remaining array for(int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMaxArr[i] = Math.Max(SuffMaxArr[i + 1], A[i + 1]); } // Stores the maximum sum of any pair int MaximumSum = Int32.MinValue; // Calculate the maximum sum for(int i = 0; i < N - 1; i++) { if (A[i] < SuffMaxArr[i]) MaximumSum = Math.Max(MaximumSum, A[i] + SuffMaxArr[i]); } // Stores the maximum sum of any pair int MinimumSum = Int32.MaxValue; // Stores the minimum of suffixes // from the given array int[] SuffMinArr = new int[N]; // Set the last element SuffMinArr[N - 1] = Int32.MaxValue; // Traverse the remaining array for(int i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMinArr[i] = Math.Min(SuffMinArr[i + 1], A[i + 1]); } // Calculate the minimum sum for(int i = 0; i < N - 1; i++) { if (A[i] < SuffMinArr[i]) { MinimumSum = Math.Min(MinimumSum, A[i] + SuffMinArr[i]); } } // Return the resultant difference return Math.Abs(MaximumSum - MinimumSum);}// Driver Codepublic static void Main(String[] args) { int[] arr = { 2, 4, 1, 3, 7, 5, 6 }; int N = arr.Length; // Function Call Console.WriteLine(GetDiff(arr, N));}}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript program for the above approach// Function to find the difference between// the maximum and minimum sum of a pair// (arr[i], arr[j]) from the array such// that i < j and arr[i] < arr[j]function GetDiff(A, N){ // Stores the maximum from // the suffix of the array let SuffMaxArr = Array(N).fill(0); // Set the last element SuffMaxArr[N - 1] = A[N - 1]; // Traverse the remaining array for(let i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMaxArr[i] = Math.max(SuffMaxArr[i + 1], A[i + 1]); } // Stores the maximum sum of any pair let MaximumSum = Number.MIN_VALUE; // Calculate the maximum sum for(let i = 0; i < N - 1; i++) { if (A[i] < SuffMaxArr[i]) MaximumSum = Math.max(MaximumSum, A[i] + SuffMaxArr[i]); } // Stores the maximum sum of any pair let MinimumSum = Number.MAX_VALUE; // Stores the minimum of suffixes // from the given array let SuffMinArr = Array(N).fill(0); // Set the last element SuffMinArr[N - 1] = Number.MAX_VALUE; // Traverse the remaining array for(let i = N - 2; i >= 0; --i) { // Update the maximum from suffix // for the remaining indices SuffMinArr[i] = Math.min(SuffMinArr[i + 1], A[i + 1]); } // Calculate the minimum sum for(let i = 0; i < N - 1; i++) { if (A[i] < SuffMinArr[i]) { MinimumSum = Math.min(MinimumSum, A[i] + SuffMinArr[i]); } } // Return the resultant difference return Math.abs(MaximumSum - MinimumSum);}// Driver Code let arr = [ 2, 4, 1, 3, 7, 5, 6 ]; let N = arr.length; // Function Call document.write(GetDiff(arr, N)); </script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
