三元组的最大值和最小值

Question

我有一个Java计算问题，其中我得到了一个整数数组：

例如：

3-2-10 0 1

我应该计算出可以从这些整数形成的最小整数和最大三元组是什么。（在这种情况下，最小值=-30，最大值=60）

我最初认为最大值总是正的，最小值总是负的。

因此，

我最初的算法是:

1. 扫描数组并取出其中的3个最大元素，存储到数组中。
2. 同时，取出里面的3个最小的元素，存储到另一个数组中。

通过不等式，我们可以推断如下：

ve = (-)(-)()或( )( )( )

-ve=（）（）（-）或（-）（-）

因此，我使用了我计算的两个数组中的元素，试图获得最大和最小三元组。（即，为了获得最大三元组，我将由最大3形成的三元组与由最小2和最大整数形成的三元组进行比较）

然而，我意识到如果所有给定的整数都是负的，我的算法就会失败，因为最大值将是负的。(对于最小值，反之亦然)

我知道我可以简单地添加更多检查来解决这个问题，或者只是使用蛮力O（N^3）解决方案。但必须有更好的方法来解决这个问题。

这个问题必须通过递归来解决，并且只能在O(N)时间内解决。

我正在修复。有人可以指导我吗？

谢谢。

Answer 1

首先，你只需要解决两个问题中的一个，比如说找到最大的三重积。有了这个你就可以通过对所有输入值求反，找到最大的三重积，求反找到答案。

所以让我们集中精力寻找最大的。你已经很好地解决了。首先取最大正数（如果有的话）。然后选择两个最大的剩余正数或两个最大的（幅度）负数中的任何一个，以乘积最大的一对为准。

如果根本没有正数，那么选择三个最小的负数。

当然，这些都可以在O(n)时间内完成，但是这不是一个递归有自然位置的算法。你必须使用简单的尾部递归来代替循环。

Answer 2

如果您在线性时间内找到3个最大值和2个最小值，则存在O（n）解。

但是您也可以使用nlog（n）排序（即快速排序）来轻松完成这项工作。

然后在这里找到C中最大乘积三元组的解决方案，并在注释中解释 -

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int solution(int A[], int N) {

long product = A[0] * A[1] * A[2];
if (N == 3) {
    return product;
}

// Nlog(N)
qsort(A, N, sizeof(int), cmpfunc);

if (A[N - 3] >= 0) {
    // if there is at least 3 non-negative value
    // then take three maximum values
    product = A[N - 1] * A[N - 2] * A[N - 3];

    if (A[1] < 0) {
        // if there is at least 2 negative value
        if (product < A[N - 1] * A[0] * A[1]) {
            // then take maximum positive and two minimum negative, if that is more than 3 positive values
            product = A[N - 1] * A[0] * A[1];
        }
    }

} else if (A[N - 1] >= 0) { 
    // else if there is least 1 non-negative value
    // then take maximum positive and two minimum negative
    product = A[N - 1] * A[0] * A[1];

} else {
    // otherwise, take 3 maximum negative values
    product = A[N - 1] * A[N - 2] * A[N - 3];
}

return product;
}