Нахождение максимального произведения элемента массива и расстояния

Вам определенно не нужно сравнивать все возможные пары, а лучше сосредоточиться на поиске максимального расстояния для каждого возможного минимального значения.

Вам больше нужно сосредоточиться на индексах, в которых возникает локальный минимум, вычислить расстояние между ними и другими элементами и пройти через массив, чтобы отслеживать самые дальние вхождения каждого элемента. Наконец, для каждого элемента вычислите произведение его значения и максимальное расстояние, которое он может создать с любым другим элементом (до или после него).

def maxProductOfMinAndDistance(a):
    n = len(a)
    left = [-1] * n
    right = [-1] * n
    
    # Initialize stack to maintain the indices of elements in the array
    stack = []
    
    # Fill left array
    for i in range(n):
        while stack and a[stack[-1]] >= a[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    
    stack = []
    
    # Fill right array
    for i in range(n-1, -1, -1):
        while stack and a[stack[-1]] >= a[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    
    # Compute the maximum product (third point)
    max_product = 0
    for i in range(n):
        if left[i] != -1:
            max_product = max(max_product, a[i] * (i - left[i]))
        if right[i] != -1:
            max_product = max(max_product, a[i] * (right[i] - i))
    
    return max_product


# Example 
a = [2, 5, 2, 2, 1, 5, 2]
print(maxProductOfMinAndDistance(a))  # Outputs 20

Вы можете попробовать это. Он имеет тот же номинальный порядок, но существенно уменьшает диапазон поиска, если a[i] мало.

Во внутренних циклах a[i] всегда является кандидатом на меньшее значение. Затем он ограничивает диапазоны поиска сверху и снизу.

Я сравнил ваше итеративное решение, а также ваш «большой» тестовый пример (который пришлось включать в код здесь немного долго).

import math

def iterative( a ):
    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))
    return res


def bestProduct( a ):
    best = 0
    lastIndex = len( a ) - 1
    for i in range( lastIndex ):
        if a[i] == 0: continue                                      # dratted edge case

        jup   = max( i + 1, math.ceil ( i + best / a[i] ) )         # reduce the search range ABOVE
        if jup <= lastIndex:
            jbest = i
            for j in range( jup, lastIndex + 1 ):
                if ( a[j] >= a[i] ): jbest = j                      # want the INDEX of the furthest that is >= a[i]
            if jbest != i: best = a[i] * ( jbest - i )

        jdown = min( i - 1, math.floor( i - best / a[i] ) )         # reduce the search range BELOW
        jbest = i
        if jdown >= 0:
            for j in range( jdown, -1, -1 ):
                if ( a[j] >= a[i] ): jbest = j
            if jbest != i: best = a[i] * ( i - jbest )

    return best


a = [2,5,2,2,1,5,2]
# a = [1,2]
# print( iterative( a ) )              # Uncomment to compare
print( bestProduct( a ) )

Вывод (простой случай):

20

Выход (большой случай):

934833

О(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)
))

Попробуйте это онлайн!

Предположим, что лучшая пара имеет меньшее или равное значение в качестве правильного значения. Для каждого правого значения найдите самое дальнее левое значение, большее или равное (так, чтобы правое значение действительно было меньше или равное) и оцените эту пару. Проделайте все это как для данного массива, так и для него в обратном порядке, что охватывает случай, когда лучшая пара имеет меньшее или равное значение в качестве левого значения.

Вдохновлен вступительным абзацем Ниджата Мурсали.