News Leaflets
A leading news portal.

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

0 17

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.

Java

  

import java.io.*;

import java.util.*;

  

public class GFG {

  

    

    

  

    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;

    }

  

    

    public static void main(String[] args)

    {

        int A[] = { 1, 1, 3 };

        int N = A.length;

        

        System.out.println(maxValue(A, N));

    }

}

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

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment