Поиск самого высокого продукта из трех чисел

Учитывая массив ints, arrayofints, найдите наивысший продукт, Highestproduct, вы можете получить из трех целых чисел. Входной массив из int всегда будет содержать как минимум три целых числа.

Итак, я вынул три цифры из arrayofints и вставил их в Highestproduct:

Highestproduct = arrayofints[:2]
for item in arrayofints[3:]:
    If min(Highestproduct) < item:
        Highestproduct[highestproduct.index(min(Highestproduct))] = item

Если min of Highestproduct меньше элемента: Замените самое низкое число на текущее число.

В итоге получится самый высокий продукт, но, видимо, есть лучшее решение. Что случилось с моим подходом? Будет ли мое решение O (n)?

Ответ 1

Следите за двумя минимальными элементами и тремя максимальными элементами, ответ должен быть min1 * min2 * max1 или max1 * max2 * max3.

Чтобы получить максимальный продукт из 3-х целых чисел, нам нужно выбрать 3 элемента максимум. Однако есть улов, что мы можем заменить 2 из наименьших из трех максимальных элементов с помощью двухминутных ints. Если оба наименьших ints отрицательны, их произведение положительно, поэтому min1 * min2 может быть больше, чем max2 * max3 (где max2 и max3 являются 2 наименьшим из 3 максимальных элементов из массива).

Это выполняется в O(n) времени.

Ответ 2

Есть некоторые уловы по этой проблеме, в списке с положительным и отрицательным int наибольшая комбинация может быть наименьшим отрицательным, вторым наименьшим отрицательным значением, наибольшим положительным значением или наибольшим положительным значением, вторым по величине положительным значением и третьим по величине стоимость;

Например, список -5,-1,1,2,3 должен возвращать 15, но когда в списке есть только отрицательные значения, это не работает, вместо того, чтобы выбирать наименьшие отрицательные целые числа, наибольшая комбинация фактически представляет собой три самых больших отрицательных значения, например: -5,-4,-3,-2,-1 должен возвращать -6. простой способ закодировать это будет просто хранить три самых больших положительных значения (считать 0 положительным),

Три наименьших отрицательных значения и три самых больших отрицательных значения при прохождении через массив, тогда мы пробуем все комбинации этих девяти чисел и получаем max. это занимает только время O(n) и O(1).

Ответ 3

Вот реализация С++ программы с временем работы O (N):

#define size 5
int A[size] = {5,4,5,10,-6};

int highest_product_of_3()
{
    int highest = max(A[0],A[1]);
    int lowest = min(A[0],A[1]);

    int highestProductOf2 = A[0]*A[1];
    int lowestProductOf2 = A[0]*A[1];

    int highestProductOf3 = A[0]*A[1]*A[2];

    for (int i=2;i<size;i++)
    {
        int current = A[i];

        // Max of 3 values:
        //                  highest_product_of_3            OR
        //                  current*highestProductOf2       OR
        //                  current*lowestProductOf2

        highestProductOf3 = max(max(highestProductOf3, current*highestProductOf2),
                                current*lowestProductOf2);

        highestProductOf2 = max(max(highestProductOf2, current*highest),
                                current*lowest);

        lowestProductOf2 = min(min(lowestProductOf2, current*highest),
                                current*lowest);

        highest = max(highest, current);        // update highest

        lowest = min(lowest, current);          // update lowest
    }


    return highestProductOf3;
}

Ответ 4

Если вы сначала сортируете arrayofints, наихудшее время работы O(n log n) вместо O(n) (т.е. не так быстро). Но код действительно короткий. А что за дружка между друзьями?

def highest_product(list_of_ints):
    if len(list_of_ints) < 3:
        return None
    sorted_ints = sorted(list_of_ints)
    return max(sorted_ints[0] * sorted_ints[1] * sorted_ints[-1], sorted_ints[-3] * sorted_ints[-2] * sorted_ints[-1])

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