题目描述

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

样例

输入: [1,2,3]
输出: 6

输入: [1,2,3,4]
输出: 24

算法

(贪心) $O(n)$ 或 $O(n \log n)$

1. 三个数的最大乘积，必然是三个最大的数的乘积或者两个最小的（负）数与最大数的乘积。
2. 通过线性扫描或者排序找出最大的三个数和最小的两个数即可。

时间复杂

• 线性扫描的时间复杂度是 $O(n)$；排序的时间复杂度是 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
    }
};