牛客题霸 [三个数的最大乘积]C++题解/答案

题目描述

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)。

题解:

有人说,排完序直接取最大的三个不就完了吗?
但是并不一定,因为负负得正,我们可以选两个负的,可能他们的绝对值更大
所以就有两种情况,一个是取最大的三个数,还一个是取最大数再乘上最小的两个数(最小的两个数有可能是负数)
然后取最大值就行

代码:

class Solution {
   
public:
    /** * 最大乘积 * @param A int整型一维数组 * @param ALen int A数组长度 * @return long长整型 */
    long long solve(int* A, int ALen) {
   
        // write code here
         sort(A,A+ALen);
        long long a = A[ALen-1]*A[ALen-2]*A[ALen-3];
        long long b = A[ALen-1]*A[0]*A[1];
        return max(a,b);
    }
};