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

Question

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

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

Например, [2, 5, 2, 2, 1, 5, 2] -> 20, (5 * (5-1)) - взята пара 5 и 5; [1, 2] -> 1

Не эффективное решение:

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)

Код не проходит по времени. Как сделать его более эффективным?

Answer 1

Набросал решение на C#. Суть в том, чтобы массив превратить в пары (значение + индекс), отсортировать по значению и пробежать от больших значений к меньшим.

var data = new[]{2, 5, 2, 2, 1, 5, 2};
var sorted = data.Select((x,i)=>(x,i)).OrderBy(x=>x).ToArray();

int min = sorted.Length-1;
int max = sorted.Length-1;  

int ret = 0;

for(int i=sorted.Length-2; i>=0; i--) {

    var test1 = sorted[i].x * Math.Abs(sorted[i].i - sorted[min].i);
    var test2 = sorted[i].x * Math.Abs(sorted[i].i - sorted[max].i);
    
    if (test1 > ret) ret = test1;
    if (test2 > ret) ret = test2;
    
    if (sorted[i].i < sorted[min].i) min = i;
    if (sorted[i].i > sorted[max].i) max = i;       
}

Console.WriteLine(ret);

Вывод в консоль: 20, получилось из за двух 5 с индексами 1 и 5, то есть 5 * (5-1) = 20.

Сложность линейно-логарифмическая из за сортировки. Если числа все небольшие, то можно и в линию уложиться.

Answer 2

Площадь прямоугольника – произведение расстояния от левой до правой границы прямоугольника на минимум их высоты. Пусть a_i и a_j - кандидаты в левые границы максимального по площади прямоугольника. Если i < j и a_i ≥ a_j, то прямоугольник с левой границей i всегда будет по площади больше прямоугольника с левой границей j.

Другими словами нет смысла проверять левые границы, которые ниже левых границ, встреченных ранее (двигаемся слева направо). Из массива a надо выбрать возрастающую подпоследовательность левых границ.

По той же причине для правых границ тоже следует выбрать возрастающую подпоследовательность значений. Только теперь мы двигаемя справа налево.

Заметим что высота максимального прамоугольника всегда равна его левой или правой границе. Для каждой левой границы в возрастающей последовательности правых отыщем, первую, которая большее или равна левой. Это и будет самый большой прямоугольник для фиксированной левой стороны.

Аналогично строится максимальный прямоугольник для фиксированной правой стороны. Когда рассмотрены все максимальные прямоугольники для всех правых и левых сторон, среди них был глобально максимальный. Задача решена, причем было просмотрено линейное количество прямогульников.

Предыдущий алгоритм выглядит сложно, его можно упростить: последовательности возрастающих сторон перевернём и смешаем с общий убывающий теперь уже список. Список перебирается от больших к меньшим высотам, поддерживается интервал индексов, ширина интервала умножается на текущую высоту. Из значений выбирается максимум.

Память - линейная (O(N)). Время тоже O(N). Сортировки нет, вместо неё отбор возрастающих подпоследовательностей (два раза). Два убывающих списка объединяются в общий убывающий список за линейное время.

import heapq


def descending(seq, key):

    def ascending(it):
        for value in it:
            yield value
            prev_k = key(value)
            break
        for value in it:
            k = key(value)
            if prev_k < k:
                yield value
                prev_k = k

    return tuple(ascending(iter(seq)))[::-1]


def candidates(a):

    def key(i):
        return a[i]

    lefts  = descending(range(len(a))      , key)
    rights = descending(range(len(a))[::-1], key)

    left  = len(a) - 1
    right = 0
    for i in heapq.merge(lefts, rights, key=key, reverse=True):
        left  = min(left , i)
        right = max(right, i)
        yield a[i] * (right - left)


print(max(candidates(tuple(map(int, input().split())))))

P.S. heapq в общем не нужен, с ним не надо писать скучный цикл слияния. Но и без него можно.

БЛОГ НА HUSL

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

Ответы (2 шт):