Дана последовательность целых чисел.

Условие

Дана последовательность целых чисел. Необходимо найти минимально возможное произведение пары элементов последовательности (пара – два каких-то элемента, не обязательно подряд идущие). Например, для последовательности чисел 9 4 2 5 3 ответ будет 6.

Ответ

Найдите два минимума и два максимума, затем сравните произведения крайних пар и минимума с максимумом. Это учитывает любые знаки и повторяющиеся значения.

def min_product(values):
    if len(values) < 2:
        raise ValueError('Need at least two elements')
    lo = sorted(values[:2])
    hi = lo[:]
    for i in range(2, len(values)):
        x = values[i]
        lo = sorted(lo + [x])[:2]
        hi = sorted(hi + [x])[-2:]
    return min(lo[0] * lo[1], hi[0] * hi[1], lo[0] * hi[1])

При разных знаках минимум отрицательный и достигается на крайних значениях. Для однознакового массива достаточно двух соответствующих крайних элементов. Сортируются лишь списки длины три: O(n) времени и O(1) дополнительной памяти.