"3 的最大乘积"问题的代码性能

Question

我正在通过一些关于Codility的问题来提高我的编码技能，我可以回答大多数问题，但下面让我感到困惑，我可以想出一个解决方案来获得预期的答案，但是当我使用非常大的数组进行测试时，它真的很慢

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

----我尝试的解决方案

----

var sum = 0;
for(int P=0; P<(A.Length-2); P++)
{
for(int Q=(P+1); Q<(A.Length-1); Q++)
{
for(int R=(Q+1); R<(A.Length); R++)
{
if ((A[P] * A[Q] * A[R]) > sum)
sum = (A[P] * A[Q] * A[R]);
}
}
}
return sum;

Answer 1

"显而易见"的解决方案是排序和计算三个最高数字的乘积以及最高数字和两个最低数字的乘积。

那么答案将是这两种产品中的最大值。

您还需要检查两个最低数字的原因是，如果它们都是负数，在这种情况下，它们的乘积将是正数(并且可能是最大乘积的一部分(。

最快的一般排序是 O(N.Log(N((，但你可以做得更好：你可以对数组进行一次传递，并记下数组中的三个最高和两个最低数字。

(注意：问题指定 3 作为数组的最小大小这一事实意味着您不必考虑少于3个元素，这简化了代码。

因此，您可以在 O(N( 时间内解决它，如下所示：

public static int MaxProduct(params int[] array)
{
int highest3 = int.MinValue; // Third highest.
int highest2 = int.MinValue; // Second highest.
int highest1 = int.MinValue; // Highest.
int lowest2  = int.MaxValue; // Second lowest.
int lowest1  = int.MaxValue; // Lowest.
foreach (int n in array)
{
if (n > highest1)
{
highest3 = highest2;
highest2 = highest1;
highest1 = n;
}
else if (n > highest2)
{
highest3 = highest2;
highest2 = n;
}
else if (n > highest3)
{
highest3 = n;
}
if (n < lowest1)
{
lowest2 = lowest1;
lowest1 = n;
}
else if (n < lowest2)
{
lowest2 = n;
}
}
// Answer is either the highest 3 or the lowest 2 and the highest 1
// (because the product of two negatives is positive).
int prodHighestOnly   = highest3 * highest2 * highest1;
int prodHighestLowest = highest1 * lowest2  * lowest1;
return Math.Max(prodHighestOnly, prodHighestLowest);
}

(本质上，highest1、highest2和highest3值是按排序顺序维护的，但作为离散变量而不是数组。

你可以这样称呼它：Console.WriteLine(MaxProduct(-3, 1, 2, -2, 5, 6));，它输出60。