给定一个整数数组arrayofints，找到三个整数的最高乘积Highestproduct。输入的整数数组将始终至少有三个整数。
因此，我从arrayofints中取出三个数字并将它们放入highestproduct中：
Highestproduct = arrayofints[:2]
for item in arrayofints[3:]:
If min(Highestproduct) < item:
Highestproduct[highestproduct.index(min(Highestproduct))] = item
如果 highestproduct 中最小的数小于当前数: 用当前数替换最小的数。
这样做可以得到最高积，但显然有更好的解决方案。我的方法有什么问题吗？我的解决方案的时间复杂度是否为O(n)？
跟踪两个最小元素和三个最大元素，答案应为 min1 * min2 * max1 或 max1 * max2 * max3。
为了得到三个整数的最大乘积，我们必须选择 3 个最大元素。但是有一个问题，我们可以用 2 个最小的 3 个最大元素中的元素替换。如果这两个最小整数都为负数，则它们的乘积为正数，因此min1 * min2可能比max2 * max3（其中max2和max3是数组中的 3 个最大元素中的 2 个）更大。
这样做的时间复杂度为 O(n)。
-5，-1，1，2，3应该返回15，但是当列表中只有负数时，这种方法不起作用，相反，选择最小的负整数，最大的组合实际上是三个最大的负数值，例如：-5，-4，-3，-2，-1应该返回-6。编写代码的简单方法是在遍历数组时，只需存储三个最大的正数值（将0视为正数），三个最小负数值和三个最大负数值，然后尝试所有这九个数字的组合并获取最大值。这只需要O(n)时间和O(1)空间。#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;
}
这种方法基本上适用于任何数量的元素，不仅仅是3个。思路是先对数组进行排序，然后取最后一个元素和倒数第二个元素的乘积。可以在Python中实现如下：
def pr(arr, n):
n = len(arr)
arr.sort()
a = {}
r = arr[n-1]
s = arr[n-2]
return {r, s}
arr = [1, 4, 3, 6, 7, 0]
q = pr(arr, 6)
print(q)
这将打印出乘积最高的元素集合。
arrayofints进行排序，则最坏情况下的运行时间为O(n log n)，而不是O(n)（即不太快）。但代码确实很短。反正朋友之间的小小log 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])