Given an array how to find the max value of
(ar[j]-ar[i]-1)*(min(ar[i],ar[j]))
in time O(n) or O(nlogn)
If the input is always nonnegative, then there is no point in using anything but the maximum element of ar as ar[j]; any product that doesn't use ar[j] there can be increased by using ar[j]. Thus, we can find the maximum value in O(n) time and try it against all possible values of ar[i] in O(n) time to solve the problem.
If the input is not required to be nonnegative, the maximum product must use the maximum ar[j] or the minimum ar[j]. Again, we can find the maximum and the minimum and try them against all possible ar[i] values.