An array of integers is given. It is necessary to find the maximum product of the distance between a pair of elements and the minimum element of this pair.
For example, [2, 5, 2, 2, 1, 5, 2] -> 20, 5 and 5 (5 * (5-1)); [1, 2] -> 1
In the first example, the maximum product is obtained if we take 5 and 5(a[1] and a[5]). The minimum element of the pair is 5. The distance between the elements: 5 - 1 = 4. Result: 5 * 4 = 20
In the second example, there is only one pair. The minimum element is 1. The distance between the elements is 1. Result: 1*1 = 1
not an effective solution:
a = [2,5,2,2,1,5,2]
res = -10**9
for i in range(len(a)-1):
for j in range(i+1,len(a)):
res = max(res, min(a[i],a[j])*(j-i))
print(res)
The code is slow to work. How can I make it more efficient?
O(n log n):
from itertools import accumulate
from bisect import bisect_left
a = [2,5,2,2,1,5,2]
print(max(
x * (j - bisect_left(m, x))
for a in [a, a[::-1]]
for m in [list(accumulate(a, max))]
for j, x in enumerate(a)
))
Assume the best pair has the smaller-or-equal value as the right value. For each right value, find the furthest left value larger or equal (so that the right value is indeed smaller or equal) and evaluate that pair. Do the whole thing both for the given array and for it reversed, which covers the case that the best pair has the smaller-or-equal value as the left value.
Inspired by Nijat Mursali's opening paragraph.