Find Maximum value of abs(i - j) * min(arr[i], arr[j]) in an array arr[] - GeeksforGeeks

Find Maximum value of abs(i - j) * min(arr[i], arr[j]) in an array arr[] - GeeksforGeeks
Given an array of n distinct elements. Find the maximum of product of Minimum of two numbers in the array and absolute difference of their positions, i.e., find maximum value of abs(i – j) * min(arr[i], arr[j]) where i and j vary from 0 to n-1.

A simple solution for this problem is to take each element one by one and compare this element with the elements on right of it. Then calculate product of minimum of them and absolute difference between their indexes and maximize the result. Time complexity for this approach is O(n^2).

An efficient solution to solves the problem in linear time complexity. We take two iterators Left=0 and Right=n-1, compare elements arr[Left] and arr[right].

left = 0, right = n-1
maxProduct = -INF
While (left < right)
    If arr[Left] < arr[right] 
        currProduct = arr[Left]*(right-Left) 
        Left++ . 
    If arr[right] < arr[Left] 
        currProduct = arr[Right]*(Right-Left) 
        Right-- . 
  
    maxProduct = max(maxProduct, currProduct)

The important thing to show that we don't miss any potential pair in above linear algorithm, i.e., we need to show that doing left++ or right-- doesn't lead to a case where we would have got higher value of maxProduct.

Please note that we always multiply with (right - left).

1) If arr[left] < arr[right], then smaller values of right for current left are useless as they can not produce higher value of maxProduct (because we multiply with arr[left] with (right - left)). What if arr[left] was greater than any of the elements on its left side. In that case, a better pair for that element must have been found with current right. Therefore we can safely increase left without missing any better pair with current left.

2) Similar arguments are applicable when arr[right] < arr[left].

int Maximum_Product(int arr[], int n)

{

    int maxProduct = INT_MIN; // Initialize result

    int currProduct; // product of current pair

 

    // loop  until they meet with each other

    int Left = 0, right = n-1;

    while (Left < right)

    {

        if (arr[Left] < arr[right])

        {

            currProduct = arr[Left]*(right-Left);

            Left++;

        }

        else // arr[right] is smaller

        {

            currProduct = arr[right]*(right-Left);

            right--;

        }

 

        // maximizing the product

        maxProduct = max(maxProduct, currProduct)

    }

 

    return maxProduct;

}

Read full article from Find Maximum value of abs(i - j) * min(arr[i], arr[j]) in an array arr[] - GeeksforGeeks