最大乘积
来源：
题目描述：
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述： 无序整数数组A[n]
输出描述：
满足条件的最大乘积
示例：
输入 4 3 4 1 2
输出
24
思路：
这道题包含三种情况，要找的这三个数全是正数，全是负数，有正有负，全是正数和全是负数都只需要最大的三个数相乘，所得的乘积就是最大的，有正有负的情况下只有两个数是负数的情况才会对乘积最大有贡献，所以我们只需要找出最大的三个数和最小的三个数，然后比较三个正数的乘积和最大正数和最小两个负数的乘积即可
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
long long a[n];
long long b,c;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
b=a[0]*a[1]*a[n-1];
c=a[n-1]*a[n-2]*a[n-3];
if(b>c){
cout<<b<<endl;
}else {
cout << c << endl;
}
return 0;
}
最后修改于 2021-01-20
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。