找到三个数字的最高产品

Question

给定一系列的int,arrayofints找到最高的产品Highestproduct,你可以得到三个整数.int的输入数组总是至少有三个整数.

所以我从中弹出了三个数字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分钟的整数替换2个最小的3个最大元素中的2个.如果两个最小的整数都是负的,那么它们的乘积是正的,因此min1 * min2可能大于max2 * max3(数组中3个最大元素中最小的2个max2和max32个).

这会O(n)及时运行.