Skip to content
Related Articles

Related Articles

Maximize the value of (A[i]-A[j])*A[k] for any ordered triplet of indices i, j and k

View Discussion
Improve Article
Save Article
  • Last Updated :03 Oct, 2022
View Discussion
Improve Article
Save Article

Given an array A consisting of N positive integersand for any ordered triplet( i, j, k) such that i, j, and k are all distinct and 0 ≤ i, j, k < N, the value of this triplet is (Ai − Aj)⋅Ak, the task is to find maximum value among all distinct ordered triplets.

Note: Two triplets (a, b, c) and (d, e, f) are considered to be different if at least one of the conditions is satisfied such that a ≠ d or b ≠ e or c ≠ f. As an example, (1, 2, 3) and (2, 3, 1) are two different ordered triplets.

Examples:

Input: A[] =  {1, 1, 3}
Output: 2

Explanation: The desired triplet is (2, 1, 0), which yields the value of (Ai−Aj)⋅Ak = (3 − 1)⋅1 = 2.

Input: A[] =  {3, 4, 4, 1, 2}
Output: 12

Approach: The problem can be solved based on the following observation:

Sort the array A in increasing order. Since we want to maximize the value of (Ai − Aj).Ak, and all elements in A are positive, it is best to maximise both (Ai − Aj) and Ak. There are two options:

  • Select largest and smallest element in A as Ai and Aj, and choose second maximum element in A as Ak. The value is (AN-1 − A0).AN−2
  • Choose the maximum element as Ak and choose the second maximum element, and the minimum element as Ai and Aj, getting a triplet of value (AN-2 − A0).AN-1

Since AN – 2 ≤ AN-1, we can prove that  (AN-1 − A0).AN−2 ≥ (AN-2 − A0).AN-1. Hence, the maximum value we can obtain is  
(AN-1 − A0).AN−2 

Follow the below steps to solve the problem:

  • Sort the array in ascending order.
  • Find the difference between the maximum and minimum element of the sorted array
  • Then multiply the difference with the second maximum element of the sorted array to get the answer.

Below is the implementation of the above approach.

C++




// C++ code to implement the approach
#include <bits/stdc++.h>
usingnamespacestd;
 
// Function to find maximum value among all distinct
// ordered tuple
longmaxValue(inta[], intn)
{
    sort(a, a + n);
    intmin = a[0];
    intmax = a[n - 1];
    intsecmax = a[n - 2];
    longans = (long)(a[n - 1] - a[0]) * a[n - 2];
    returnans;
}
 
// Driver Code
intmain()
{
    intA[] = { 1, 1, 3 };
    intN = sizeof(A) / sizeof(A[0]);
   
    // Function call
    cout << maxValue(A, N);
    return0;
}
 
// This code is contributed by aarohirai2616.

Java




// Java code to implement the approach
 
importjava.io.*;
importjava.util.*;
 
publicclassGFG {
 
    // Function to find maximum value among all distinct
    // ordered tuple
    publicstaticlongmaxValue(inta[], intn)
    {
        Arrays.sort(a);
        intmin = a[0];
        intmax = a[n - 1];
        intsecmax = a[n - 2];
        longans = (long)(a[n - 1] - a[0]) * a[n - 2];
        returnans;
    }
 
    // Driver code
    publicstaticvoidmain(String[] args)
    {
        intA[] = { 1, 1, 3};
        intN = A.length;
        // Function call
        System.out.println(maxValue(A, N));
    }
}

Python3




# Python code to implement the approach
 
# Function to find maximum value among all distinct ordered tuple
defmaxValue(a, n):
    a.sort()
    min=a[0]
    max=a[n -1]
    secmax =a[n -2]
    ans =(a[n -1] -a[0]) *a[n -2]
    returnans
 
# Driver Code
if__name__ =='__main__':
    A =[1, 1, 3]
    N =len(A)
 
    # Function call
    print(maxValue(A, N))
 
    # This code is contributed by aarohirai2616.

C#




usingSystem;
 
publicclassGFG
{
 
  // Function to find maximum value among all distinct
  // ordered tuple
  publicstaticlongmaxValue(int[] a, intn)
  {
    Array.Sort(a);
    longans = (long)(a[n - 1] - a[0]) * a[n - 2];
    returnans;
  }
 
  // Driver code
  staticpublicvoidMain()
  {
    int[] A = { 1, 1, 3 };
    intN = A.Length;
     
    // Function call
    Console.WriteLine(maxValue(A, N));
  }
}
 
// This code is contributed by Rohit Pradhan

Javascript




<script>
 
// JavaScript code to implement the approach
 
    // Function to find maximum value among all distinct
    // ordered tuple
    functionmaxValue(a, n)
    {
        a.sort();
        let min = a[0];
        let max = a[n - 1];
        let secmax = a[n - 2];
        let ans = (a[n - 1] - a[0]) * a[n - 2];
        returnans;
    }
 
 
// Driver Code
        let A = [ 1, 1, 3 ];
        let N = A.length;
         
        // Function call
        document.write(maxValue(A, N));
 
// This code is contibuted by sanjoy_62.
</script>
Output
2

Time Complexity: O(N * log(N)) 
Auxiliary Space: O(1)


My Personal Notesarrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!