寻找三个数的最高乘积

Question

给定一个整数数组arrayofints，找到最高的积Highestproduct，您可以从三个整数中得到。整数的输入数组将始终至少有三个整数。

所以我从arrayofints中弹出了三个数字，并将它们插入highestproduct：

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

如果min的highestproduct小于项：用当前数替换最低数。

这最终会得到最高的产品，但显然有更好的解决方案。我的方法怎么了？我的解决方案是O（n）吗？

Answer 1

跟踪两个最小元素和三个最大元素，答案应该是min1 * min2 * max1或max1 * max2 * max3。

要得到3个整数的最大乘积，我们必须选择3个最大元素。但是有一个陷阱，我们可以用2个最小的整数替换3个最大元素中的最小元素中的2个。如果两个最小的int都是负的，则它们的乘积是正的，因此min1 * min2可能大于max2 * max3（其中max2和max3是数组中3个最大元素中最小的2个）。

这将在O(n)时间内运行。

Answer 2

这里是一个C++程序实现，程序运行时间为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;
}

Answer 3

在一个包含正整数和负整数的列表中，最大的组合可以是最小的负整数、第二个最小的负整数、最大的正整数或最大的正整数、第二个最大的正整数和第三个最大的正整数

例如，-5,-1,1,2,3的列表应该返回15，但是当列表中只有负值时，这不起作用，与其选择最小的负整数，大数组合实际上是三个最大的负值，例如：-5,-4,-3,-2,-1应该返回-6。编写代码的简单方法是只存储三个最大的正值（将0视为正值）

三个最小的负值和三个最大的负值，然后我们尝试这九个数字的所有组合，得到最大值，这只需要O(n)时间和O(1)空间。