欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网机试题-最大乘积

程序员文章站 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;
}
相关标签: 数据结构与算法