牛客网机试题-最大乘积
程序员文章站
2024-03-17 14:38:40
...
题目描述
给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)
输入描述:
数组元素个数n
无序整数数组A[n]
输出描述:
满足条件的最大乘积
示例1
输入
4
3 4 1 2
输出
24
思路
定义五个数,一个最大,一个次大,一个第三大,一个最小,一个次小。只要找到这五个数,问题就解决了。因为最大乘积只可能是最大×次大×第三大 或者是 最大×最小×次小
代码
#include<iostream>
#include<limits.h>
using namespace std;
int main(){
long long min_fir=INT_MAX,min_sec=INT_MAX;
long long max_fir=INT_MIN,max_sec=INT_MIN,max_third=INT_MIN;
int n;
cin>>n;
int A[n];
for(int i=0;i<n;i++){
cin>>A[i];
if(A[i]<min_fir){
min_sec=min_fir;
min_fir=A[i];
}
else if(A[i]<min_sec){
min_sec=A[i];
}
if(A[i]>max_fir){
max_third=max_sec;
max_sec=max_fir;
max_fir=A[i];
}
else if(A[i]>max_sec){
max_third=max_sec;
max_sec=A[i];
}
else if(A[i]>max_third)
max_third=A[i];
}
long long res=max_fir*max_sec*max_third>max_fir*min_fir*min_sec?max_fir*max_sec*max_third:max_fir*min_fir*min_sec;
cout<<res;
}
上一篇: 进制转换_小数
下一篇: PAT A1010 Radix