题目的主要信息：

给定一个长度为 n 的无序数组 A ，包含正数、负数和 0
找出 3 个数，使得乘积最大，返回这个乘积

方法一：排序法

具体做法：

如果数组全是正数，则数组最大的三个数相乘乘积最大；
如果数组全是负数，则数组最大的三个数相乘乘积最大；
如果数组只有1个正数，其余都是负数，则数组最小的两个数再乘上正数乘积最大；
如果数组只有2个正数，其余都是负数，则数组最小的两个数再乘上较大的正数乘积最大；
如果数组只有1个负数，其余都是正数，则数组最大的三个数乘积最大；
如果数组有两个及以上的负数和三个及以上的正数，则最大值可能是三个最大的正数相乘，也可能是最小的两个负数乘积再乘上最大的一个正数；

综上所述，我们只需要找到最大的三个数和最小的两个数，比较两种乘积即可得到最大乘积。利用排序，有序数组前两个数最小，后三个数最大。

class Solution {
public:
    long long solve(int* A, int ALen) {
        sort(A, A + ALen); //排序
        return max((long long)(A[0] * A[1] * A[ALen - 1]), (long long)(A[ALen - 1] * A[ALen - 2] * A[ALen - 3])); //选取最大的情况
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，需要对数组进行排序，sort函数属于快排
空间复杂度： $O (1)$ ，无额外空间

方法二：查找法

具体做法：

既然是要找最大的三个数和最小的两个数，我们遍历一次也可以解决。首先遍历数组，检查每个元素，如果该值小于第一小的元素，则用第一小的元素更新第二小的元素，然后将该元素暂时作为第一小的元素，继续后续的遍历；如果该值不小于第一小的元素但是小于第二小的元素，则直接将该元素作为第二小的元素即可。检查最大的三个元素，方法类似，还是依次比较替换即可。

最后得到三个最大的正数相乘以及最小的两个负数乘积再乘上最大的一个正数，比较最大值即可。

alt

class Solution {
public:
    long long solve(int* A, int ALen) {
        long long max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN; //记录数组第一大、第二大、第三大
        long long min1 = INT_MAX, min2 = INT_MAX; //记录数组第一小、第二小
        for(int i = 0; i < ALen; i++){
            if(A[i] < min1){ //首先查看是否比第一小还小
                min2 = min1;
                min1 = A[i];
            }else if(A[i] < min2) //再看不如第一小的情况下是否比第二小要小
                min2 = A[i];
            if(A[i] > max1){ //首先看是否比第一大还大
                max3 = max2;
                max2 = max1;
                max1 = A[i];
            }else if(A[i] > max2){ //再看不如第一大的情况下是否比第二大要大
                max3 = max2;
                max2 = A[i];
            }else if(A[i] > max3) //最后看不如第二大的情况下是否比第三大要大
                max3 = A[i];
        }
        return max(max1 * max2 * max3, min1 * min2 * max1); //选取二者中最大的乘积
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，仅遍历一次数组
空间复杂度： $O (1)$ ，无额外空间

题解 | #三个数的最大乘积#

题目的主要信息：

方法一：排序法

方法二：查找法