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

• Last Updated :03 Oct, 2022

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 ``using``namespace``std;` `// Function to find maximum value among all distinct``// ordered tuple``long``maxValue(``int``a[], ``int``n)``{``    ``sort(a, a + n);``    ``int``min = a;``    ``int``max = a[n - 1];``    ``int``secmax = a[n - 2];``    ``long``ans = (``long``)(a[n - 1] - a) * a[n - 2];``    ``return``ans;``}` `// Driver Code``int``main()``{``    ``int``A[] = { 1, 1, 3 };``    ``int``N = ``sizeof``(A) / ``sizeof``(A);``  ` `    ``// Function call``    ``cout << maxValue(A, N);``    ``return``0;``}` `// This code is contributed by aarohirai2616.`

## Java

 `// Java code to implement the approach` `import``java.io.*;``import``java.util.*;` `public``class``GFG {` `    ``// Function to find maximum value among all distinct``    ``// ordered tuple``    ``public``static``long``maxValue(``int``a[], ``int``n)``    ``{``        ``Arrays.sort(a);``        ``int``min = a[``0``];``        ``int``max = a[n - ``1``];``        ``int``secmax = a[n - ``2``];``        ``long``ans = (``long``)(a[n - ``1``] - a[``0``]) * a[n - ``2``];``        ``return``ans;``    ``}` `    ``// Driver code``    ``public``static``void``main(String[] args)``    ``{``        ``int``A[] = { ``1``, ``1``, ``3``};``        ``int``N = 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``def``maxValue(a, n):``    ``a.sort()``    ``min``=``a[``0``]``    ``max``=``a[n ``-``1``]``    ``secmax ``=``a[n ``-``2``]``    ``ans ``=``(a[n ``-``1``] ``-``a[``0``]) ``*``a[n ``-``2``]``    ``return``ans` `# 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#

 `using``System;` `public``class``GFG``{` `  ``// Function to find maximum value among all distinct``  ``// ordered tuple``  ``public``static``long``maxValue(``int``[] a, ``int``n)``  ``{``    ``Array.Sort(a);``    ``long``ans = (``long``)(a[n - 1] - a) * a[n - 2];``    ``return``ans;``  ``}` `  ``// Driver code``  ``static``public``void``Main()``  ``{``    ``int``[] A = { 1, 1, 3 };``    ``int``N = A.Length;``    ` `    ``// Function call``    ``Console.WriteLine(maxValue(A, N));``  ``}``}` `// This code is contributed by Rohit Pradhan`

## Javascript

 ``
Output
`2`

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

My Personal Notesarrow_drop_up