1.题目描述
给定一个无序数组，包含正数、负数和 0，要求从中找出 3 个数的乘积，使得乘积最大，要求时间复杂度： O(n)，空间复杂度：O(1)
- 输入描述:
第一行是数组大小 n，第二行是无序整数数组 A[n]。n >=3 - 输出描述:
满足条件的最大乘积 - 输入示例:
4 3 4 1 2 - 输出示例:
24
2.题目解析
数列有以下三种情况：
- 全是正数
- 全是负数
- 有正有负
乘积最大只有两种情况：
- 三个最大正数
- 一个最大整数和两个最小负数
问题最终归结为找出这五个数比较乘积即可。
3.参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0;
scanf("%d",&n);
long long nums[n];
fill_n(nums,n,0);
for(int i=0;i<n;++i){
scanf("%lld",&nums[i]);
}
sort(nums,nums+n);
long m = max(nums[n-1]*nums[n-2]*nums[n-3],nums[n-1]*nums[0]*nums[1]);
printf("%lld",m);
return 0;
}
注意:两个long数字相乘，结果可能大于long最大值，所以，乘积放入long long，防止溢出。
