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

https://www.geeksforgeeks.org/find-maximum-value-of-absi-j-minarri-arrj-in-an-array-arr/

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.
Examples :

Input : arr[] = {3, 2, 1, 4}
Output: 9
// arr[0] = 3 and arr[3] = 4 minimum of them is 3 and 
// absolute difference between their position is 
// abs(0-3) = 3. So product is 3*3 = 9

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)

How does this work?
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].

For those having same doubt consider this explanation

My doubt:

Now if arr[leftpointer] is smaller we increment left pointer else increment right
pointer. we increment left pointer because any element to left of right
pointer, greater than arr[left pointer] will yield smaller value of
abs(i – j) so we do not need to consider those cases.

that logic was correct

BUT

BUT what about those elements to right of right pointer and greater than
arr[left pointer] may yield a larger value for abs(i – j) which we are
missing to consider.?

Explanation:

those elements to the right of rightPointer but greater than arr[leftPoiner] will definetely yield greater value of abs(j-i) than current abs(rightPointer -leftPoiner) but think that

that element to right of right pointer greater than arr[left Pointer] will never be paired with this arr[left Pointer] because it has been previously been paired with some element to left of left pointer which was greater than this right element so that pairing computed a greater value of abs(i – j) * min(arr[i], arr[j]) than pairing that element with this arr[left Pointer].

Similar argument for elements to left of left pointer

example

{12,9,13,11}

i refer to left pointer

j refer to right pointer

step 1

i = 0 j = 3 output decremnet j because arr[j] < arr[i]

i = 0 j = 2 output incremnet i because arr[i] < arr[j]

i = 1j = 2 Now you may consider here we must consider pairing {9,11} instead of {9,13}
because for {9,11} value of abs(j-i) is greater than for {9,13} with same value of min(A[i],A[j]) but 11 won't be ever paired with 9 because it was earlier paired with 12 > 11

yielding a value 11*3 which is greater than that it can achieve pairing it with 9 which 9*2

    static int Maximum_Product(int arr[], int n) {

          

    // Initialize result

    int maxProduct = Integer.MIN_VALUE; 

      

    // product of current pair

    int currProduct;            

  

    // 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++;

    } 

      

    // arr[right] is smaller

    else 

    {

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

        right--;

    }

  

    // maximizing the product

    maxProduct = Math.max(maxProduct, currProduct);

    }

  

    return maxProduct;

}