Given an array A consisting of N positive integers and 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>using namespace std;// Function to find maximum value among all distinct// ordered tuplelong maxValue(int a[], int n){ sort(a, a + n); 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 Codeint main(){ int A[] = { 1, 1, 3 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << maxValue(A, N); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport 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 tupledef 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 Codeif __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[0]) * 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
<script>// JavaScript code to implement the approach // Function to find maximum value among all distinct // ordered tuple function maxValue(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]; return ans; }// Driver Code let A = [ 1, 1, 3 ]; let N = A.length; // Function call document.write(maxValue(A, N));// This code is contributed by sanjoy_62.</script> |
2
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
